[白俊解答問題]#11657

11657:タイムマシン
https://www.acmicpc.net/problem/11657
問題を解く
1つの頂点から別の頂点までの最短距離を求めるアルゴリズム.負の幹線が存在するため,ベルマンフォードアルゴリズムを用いた.ベルマンフォードアルゴリズムは,開始点から1本の幹線を用いる最短距離からV−1本の幹線を用いる最短距離(V個の頂点を有する図形では,最短経路がV−1本の幹線を用いることが多い)を繰り返し文により解く.このとき、負周期があるかどうかを確認するために、実際の繰り返し文はV回繰り返し、V回繰り返しで上限が初期化されていれば、負周期があることを確認し、始点頂点に関連付けることができる.
コード#コード#

#include <cstdio>
#include <vector>

using namespace std;

const int INF = 987654321;

int n, m;
vector<vector<pair<int, int>>> adj;

vector<long long> bellmanFord(int src) {
    vector<long long> upper(n + 1, INF);
    upper[src] = 0;
    bool updated;
    for(int iter = 0; iter < n; iter++) {
        updated = false;
        for(int here = 1; here <= n; here++) {
            if(upper[here] == INF) continue;
            for (int i = 0; i < adj[here].size(); i++) {
                int there = adj[here][i].first;
                int cost = adj[here][i].second;
                if(upper[here] + cost < upper[there]) {
                    updated = true;
                    upper[there] = upper[here] + cost;
                }
            }
        }
        if(!updated) break;
    }
    if(updated) upper.clear();
    return upper;
}

int main() {
    scanf("%d %d", &n, &m);
    adj.resize(n + 1);
    for(int i = 0; i < m; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back(make_pair(b, c));
    }
    vector<long long> dist = bellmanFord(1);
    if(dist.size() == 0) printf("-1");
    else {
        for(int city = 2; city <= n; city++)
            if(dist[city] == INF) printf("-1\n");
            else printf("%d\n", dist[city]);
    }
}

学識
都市の個数は最大500個で、最大500個の頂点の負の周期があり、最大1回の繰り返しドアは-1000*500を緩和することができるので、上位はlong long型であるべきだ.