路地裏

白駿1738号:路地

アイデア

負の幹線を含む最短距離を探します.
この場合,単にループが存在するからといって−1を出力するのではなく,1からNへの経路にループが存在し,Nに到達したときに無限に金銭を持ち運ぶことができるときのみ−1を出力する.
例えば、N=5であり、1−>2,2−>3,3−>4,4−>3,1−>5の幹線を有する.3->4,4->3が負の周期であっても、1からNへの道は1->5であり、3,4で無限のお金を持っていても、この状態でNに到達することはできないので、-1を出力することはできません.
どのようにNに着く道で循環があるかどうかを判別しますか?
ループが存在する場合、ノードのdistは負に無限大になります.Nへの道にこの周期が含まれていれば,dist[N]は最終的に負の無限大になる.
入力を受けた時に逆の料金(お金を拾った時はマイナス、奪われた時はプラス)を受け取った.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 101;
constexpr long long INF = 1e18;
int N, M;
vector<pair<int, long long>> adj[MAX];
long long dist[MAX];
int pnode[MAX];

void solve() {
    fill(dist, dist+MAX, INF);
    dist[1] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N+1; j++) {
            for (auto p : adj[j]) {
                if (dist[j] != INF && dist[p.first] > dist[j] + p.second) {
                    dist[p.first] = dist[j] + p.second;
                    pnode[p.first] = j;
                    if (i == N-1) {
                        dist[p.first] = -INF;
                    }
                }
            }
        }
    }
    // N까지 가는 길이 존재하지 않는 경우 || N까지 가는 길에 사이클이 존재하는 경우
    if (dist[N] == INF || dist[N] == -INF) cout << -1;
    else {
        int x = N;
        vector<int> v;
        while (x != 0) {
            v.push_back(x);
            x = pnode[x];
        }
        for (auto i = v.rbegin(); i != v.rend(); i++) {
            cout << *i << ' ';
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, -c});
    }
    solve();
    return 0;
}

おしゃべり

図形全体にループが存在するか否かを判断するのではなく,目的地に到達する経路にループが存在するか否かを判断する場合に,このように解く.
都市番号順に印刷されていると思っていましたが、そうではありません.私の2時間です.