Bellman_Ford

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1865 🧐 관찰 및 접근 # 무향인 도로와 유향인 웜홀이 있고, 음수 사이클이 있는지를 체크하는 문제이다. $N \leq 500$으로 크지 않으므로, 플로이드 워셜도 충분히 돈다. 이건 $O(N^3)$ 하지만 벨만포드로 $O(VE)$로 더 빠르게도 풀 수 있다. 벨만포드가 된다는건 SPFA로도 더 빠르게 풀 수 있다! 다 해본 결과, 플로이드워셜이 496ms, 벨만포드가 24ms, SPFA가 12ms가 나왔다. 💻 풀이 # 코드 (C++): void solve(){ int N, M, W; cin >> N >> M >> W; vector<vector<ll>> cost(N, vector<ll>(N, 1e15)); rep(i, 0, N) cost[i][i] = 0; rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = min(cost[u][v], w); cost[v][u] = min(cost[v][u], w); } rep(i, 0, W){ ll u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = min(cost[u][v], -w); } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); rep(i, 0, N) if(cost[i][i] < 0){ cout << "YES\n"; return; } cout << "NO\n"; } 🔒 구현 코드 잠금