Submission #1382698

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF = 1e15;
struct edge{int from, to; ll cost;

  edge (int f, int t, ll c) : from(f), to(t), cost(c) {}

};

int N,M;
vector<edge> e;
ll dist[1001];

int main() {
  cin >> N >> M;

  for(int i = 0; i < M; i++) {
    int a,b;
    ll c;
    cin >> a >> b >> c;
    a--; b--;
    e.push_back(edge(a,b,-c));
  }

 
  fill(dist,dist+N,INF);
  bool is = true;
  dist[0] = 0;
  int C = 0;
  for(int j = 0; j < N; j++) {
    for(int i = 0; i < e.size(); i++) {
      if(dist[e[i].from] == INF) continue;

      if(dist[e[i].to] > dist[e[i].from] + e[i].cost){
	dist[e[i].to] = dist[e[i].from] + e[i].cost;
	is = true;
	//	cout <<dist[e[i].to]<<endl;
	
      }
    }
  }
  ll heiro = dist[N-1];

   for(int j = 0; j < N; j++) {
    for(int i = 0; i < e.size(); i++) {
      if(dist[e[i].from] == INF) continue;

      if(dist[e[i].to] > dist[e[i].from] + e[i].cost){
	dist[e[i].to] = dist[e[i].from] + e[i].cost;
	is = true;
	//	cout <<dist[e[i].to]<<endl;
	
      }
    }
  }

   if(heiro <= dist[N-1]) {
     cout <<-dist[N-1] <<endl;
   }
   else cout <<"inf"<<endl;

}

  
  
  

Submission Info

Judge Result