백준 25953번 템포럴 그래프

문제 링크

문제에 적혀있는 대로, 각 $T$마다 간선 완화를 딱 한 번 할 수 있다.

때문에 dist배열을 하나만 놓고 쓰면 안되고, 각 $T$마다 따로 놓고 써야한다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, t, m, s, e;
int dist[10000];
vector<vector<pair<int, int>>> adj[1000];

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

    cin >> n >> t >> m >> s >> e;
    for (int i = 0; i < t; i++) {
        adj[i].resize(n);
        for (int j = 0; j < m; j++) {
            int a, b, c;
            cin >> a >> b >> c;
            adj[i][a].emplace_back(b, c);
            adj[i][b].emplace_back(a, c);
        }
    }

    fill(dist, dist+10000, 1e9);
    dist[s] = 0;
    for (int i = 0; i < t; i++) {
        int tmp[10000];
        copy(dist, dist+10000, tmp);
        for (int j = 0; j < n; j++) {
            if (dist[j] == 1e9) continue;
            for (auto [next, cost] : adj[i][j]) {
                if (dist[next] > dist[j] + cost) {
                    tmp[next] = dist[j] + cost;
                }
            }
        }
        copy(tmp, tmp+10000, dist);
    }

    if (dist[e] == 1e9) cout << -1;
    else cout << dist[e];

    return 0;
}

약간 벨만 포드 느낌이다. 그래프 최단경로 알고리즘 정리에서 알아보도록 하자. 이렇게 인접 리스트로 입력받는 방식 말고, 간선만 따로 입력받아도 상관 X.