Submission #1521301

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;


struct Edge {
    int to, cost;

};
typedef vector<vector<Edge> > AdjList;
AdjList graph;

const long long INF = -1000000000000000000;

vector<long long> dist;


bool bellman_ford(int n, int s){
    dist = vector<long long>(n,INF);
    dist[s] = 0;
    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-1){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(void){
    int n, m;
    cin >> n >> m;

    graph = AdjList(n);

    for(int i=0;i<m;i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        from--;
        to--;
        graph[from].push_back((Edge){to,cost});
    }

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

    return 0;
}

Submission Info

Judge Result