Submission #1286858

---

Source Code Expand

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

void print2d(vector<string> M){
    cout << endl;
    for(string s: M){
        cout << s << endl;
    }
}

// 隣接リストで使う辺を表す型
struct Edge {
    int to, cost;  // 辺の接続先頂点, 辺の重み
    Edge(int to, int cost) : to(to), cost(cost) {}  // コンストラクタ
};

typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
AdjList graph;  // グラフの辺を格納した構造体
// graph[v][i]は頂点vから出るi番目の辺Edge

const long INF = numeric_limits<long>::max();

vector<long> dist;

// 戻り値がtrueなら負の閉路を含む
bool bellman_ford(int n, int s) { // nは頂点数、sは開始頂点
    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; // n回目にも更新があるなら負の閉路が存在
                }
            }
        }
    }
    return false;
}

int main(int argc, const char * argv[]) {
    
    int n, m;
    cin >> n >> m;
    
    dist = vector<long>(n, INF);
    dist[0] = 0; // 開始点の距離は0
    
    graph = AdjList(n);
    
    for (int i = 0; i < m; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        
        from -= 1;
        to -= 1;
        cost *= -1;
        
        graph[from].push_back(Edge(to, cost));
    }
    
    bool result = bellman_ford(n, 0);
    
    if(result == true){
        long old = dist[n-1];
        bellman_ford(n, 0);
        if(old == dist[n-1]){
            cout << -dist[n-1] << endl;
        }else{
            cout << "inf" << endl;
        }
    }else{
        cout << -dist[n-1] << endl;
    }
    return 0;
}

Submission Info

Judge Result