Submission #1777223

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = (1LL << 50) * -1;
struct edge {
  int from, to, cost;
};
int main(void) {
  int n, m;
  cin >> n >> m;
  vector<edge> graph(m);
  vector<ll> distance(n, INF);
  distance[0] = 0;
  for (int i = 0; i < m; i++) {
    cin >> graph[i].from;
    cin >> graph[i].to;
    graph[i].from--;
    graph[i].to--;
    cin >> graph[i].cost;
  }
  bool update;
  vector<bool> initial(n, 1);
  for (int loop = 0; loop < n; loop++) {
    update = false;
    for (int i = 0; i < m; i++) {
      if (initial[graph[i].from] == INF) continue;
      if (distance[graph[i].to] < distance[graph[i].from] + graph[i].cost) {
        distance[graph[i].to] = distance[graph[i].from] + graph[i].cost;
        update = true;
      }
    }
  }
  //if (update) {
  //  cout << "inf" << endl;
  //} else {
    cout << distance[n - 1] << endl;
  //}
  return 0;
}

Submission Info

Judge Result