# 문제 분류
최단 경로 알고리즘
양의 경로와 음의 경로를 바꿔준다. 경로는 양인게 부정적인 것이니까 이정도는 바로 생각해낼 수 있다. 문제는 사이클인데, 경로에 해당하지 않지만 사이클이 존재할 수 있는 가능성이 있다. 그런 경우 -1을 내주면 안되기 때문에 BFS를 돌리고 해준다. 첫 시도는 SPFA로 했는데 안되더라.. 왜지 ? 질문에도 올라가있다.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, u, v, w;
const int MAX_V = 2e5 + 10;
vii adj[MAX_V];
vi rev[MAX_V];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
fup(i, 1, M, 1) {
cin >> u >> v >> w;
adj[u].pb({v, -w});
rev[v].pb(u);
}
queue<int> qz;
qz.push(N);
int visited[MAX_V] = {0};
visited[N] = 1;
while (!qz.empty()) {
int curr = qz.front();
qz.pop();
for (int next : rev[curr]) {
if (!visited[next]) {
visited[next] = 1;
qz.push(next);
}
}
}
if (!visited[N]) {
cout << -1;
return 0;
}
int prev[MAX_V];
ll dist[MAX_V];
fill(dist, dist + MAX_V, INF);
dist[1] = 0;
fup(i, 1, N, 1) {
fup(j, 1, N, 1) {
for (auto &p : adj[j]) {
int next = p.X;
int cost = p.Y;
if (dist[j] != INF && dist[next] > dist[j] + cost) {
dist[next] = dist[j] + cost;
prev[next] = j;
// 방문할 수 없는 사이클의 경우 포함하지 않는다.
if (i == N && visited[next]) {
cout << -1;
return 0;
}
}
}
}
}
if (dist[N] == INF) {
cout << -1;
} else {
vi path;
for (int i = N; i > 0; i = prev[i]) {
path.pb(i);
}
reverse(path.begin(), path.end());
for (int s : path) {
cout << s << " ";
}
}
}