Submission #1521631

---

Source Code Expand

#include <iostream>
#include <vector>
#define ll long long
#define INF 100000000000000000
#define MAX 100010
using namespace std;

struct edge{
  int to;
  ll cost;
};

typedef pair<ll, int> p;
vector<edge> graph[MAX];
vector<ll> dist;

bool bellman_ford(int n){ //nは頂点数
  for(int i = 0; i < n; i++){
    for(int v = 0; v < n; v++){
      for(int k = 0; k < graph[v].size(); k++){
        edge e = graph[v][k];
        if(dist[v] != INF && dist[e.to] > dist[v] + e.cost){
          dist[e.to] = dist[v] + e.cost;
          if(i == n) return true; // 負の回路が存在
        }
      }
    }
  }
  return false;
}

int main(){
  int v, e, s, t;
  ll d;
  cin >> v >> e;
  for(int i = 0; i < e; i++){
    cin >> s >> t >> d;
    s--; t--;
    graph[s].push_back((edge){t, -d});
  }
  dist = vector<ll>(v, INF); //distをINFで初期化
  dist[0] = 0;
  bellman_ford(v);
  ll tmp = -dist[v-1];
  bellman_ford(v);
  if(tmp < -dist[v-1]){
    cout << "inf" << endl;
  }else{
    cout << -dist[v-1] << endl;
  }
  return 0;
}

Submission Info

Judge Result