Submission #1382735

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define N_MAX 1000
#define INF (1LL << 50)
 
using namespace std;
 
typedef long long ll;
 
struct EDGE{
  int to;
  ll cost;
 
  EDGE(int t, ll c){
    to = t;
    cost = c;
  }
 
};
 
typedef vector<vector<EDGE> > AdjList;
 
AdjList v;
int n, m;
ll d[N_MAX+1];
 
bool bellman_ford(int n){
  int cnt = 0;
  rep(i, N_MAX+1){
    d[i] = INF;
  }
 
  d[0] = 0;
 
  rep(i, n){
    rep(j, n){
      rep(k, v[j].size()){
	EDGE e = v[j][k];
	if(d[j] != INF && (d[e.to] > d[j] + e.cost)){
	  d[e.to] = d[j] + e.cost;
	  //if(i == n) return true;
	}
      }
    }
  cnt++;
  }
 
  return (cnt == n-1)?true:false;
}
 
signed main(){
 
  int from, to;
  ll cost;
 
  cin >> n >> m;
 
  v = AdjList(n);
  rep(i, m){
    cin >> from >> to >> cost;
    v[from-1].pb(EDGE(to-1, -cost));
  }
 
 
  if(bellman_ford(n) || d[n-1] == INF){
    cout << "inf" << endl;
  }else{
    cout << -d[n-1] << endl;
  }
 
 
}

Submission Info

Judge Result