Submission #1384468

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

#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 -1000000000000

typedef long long ll;

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> edges;
ll d[N_MAX+1];

bool bellman_ford(){
  rep(i, N_MAX+1) d[i] =-INF;
  d[0] = 0;
  rep(i, 2*n+1){
    for(auto &edge:edges){
      if(d[edge.from] != INF && d[edge.to] < d[edge.from] + edge.cost){
        d[edge.to] = d[edge.from] + edge.cost;
        if(i == n-1) return true;
      }
    }
  }
  return false;
}

signed main(){
  int f, t;
  ll c;
  cin >> n >> m;

  rep(i, m){
    cin >> f >> t >> c;
    f--; t--;
    edges.emplace_back(f, t, c);    
  }

  if(bellman_ford()){
    cout << "inf" << endl;
  }else{
    cout << d[n-1] << endl;
  }
}

Submission Info

Judge Result