Submission #1609365

---

Source Code Expand

#include<bits/stdc++.h>
#define INF 1e18
#define int long long
using namespace std;
typedef pair<int,int> P;

struct Graph{
  Graph(int n):E(n),d(n){};
  vector<vector<P>>E;
  vector<int>d;
  void add_edge(int a,int b,int c){
    E[a].push_back({b,c});
  }
  bool bellmanFord(int s,int t){
    int N=d.size();
    fill(d.begin(),d.end(),INF);
    d[s]=0;
    for(int i=0;i<N;++i)
      for(int j=0;j<N;++j)
        for(P& p:E[j])
          if(d[j]!=INF&&d[j]+p.second<d[p.first]){
            d[p.first]=d[j]+p.second;
            if(i==N-1&&p.first==t)return false;
            //if check after destination route
            // if(i==N-1)return false;
          }
    return true;
  }
  int get_cost(int n){
    return d[n];
  }
};

main(){
  int n,m,a,b,c;
  cin>>n>>m;
  Graph G(n);
  for(int i=0;i<m;++i){
    cin>>a>>b>>c;
    G.add_edge(a-1,b-1,-c);
  }
  if(G.bellmanFord(0,n-1))cout<<-G.get_cost(n-1)<<endl;
  else cout<<"inf"<<endl;
}


/***************************

ABC061_D
http://abc061.contest.atcoder.jp/tasks/abc061_d

****************************/

Submission Info

Judge Result