📝 문제 정보#
🧐 관찰 및 접근#
- 무향인 도로와 유향인 웜홀이 있고, 음수 사이클이 있는지를 체크하는 문제이다.
- $N \leq 500$으로 크지 않으므로, 플로이드 워셜도 충분히 돈다.
- 이건 $O(N^3)$
- 하지만 벨만포드로 $O(VE)$로 더 빠르게도 풀 수 있다.
- 벨만포드가 된다는건 SPFA로도 더 빠르게 풀 수 있다!
- $N \leq 500$으로 크지 않으므로, 플로이드 워셜도 충분히 돈다.
- 다 해본 결과, 플로이드워셜이 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";
}void solve(){
int N, M, W; cin >> N >> M >> W;
vector<vector<pll>> links(N);
rep(i, 0, M){
ll u, v, w; cin >> u >> v >> w;
u--; v--;
links[u].push_back({v, w});
links[v].push_back({u, w});
}
rep(i, 0, W){
ll u, v, w; cin >> u >> v >> w;
u--; v--;
links[u].push_back({v, -w});
}
vector<ll> dist(N, 0);
dist[0] = 0;
bool negCycle = false;
rep(i, 0, N){
for(int u = 0; u < N; u++){
for(auto [v, w] : links[u]){
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
if(i == N-1) negCycle = true;
}
}
}
}
if(negCycle) cout << "YES\n";
else cout << "NO\n";
}void solve(){
int N, M, W; cin >> N >> M >> W;
vector<vector<pll>> links(N);
rep(i, 0, M){
ll u, v, w; cin >> u >> v >> w;
u--; v--;
links[u].push_back({v, w});
links[v].push_back({u, w});
}
rep(i, 0, W){
ll u, v, w; cin >> u >> v >> w;
u--; v--;
links[u].push_back({v, -w});
}
// SPFA
vector<ll> dist(N, 0);
vector<int> cnt(N, 0);
vector<bool> inQ(N, false);
queue<int> Q;
rep(i, 0, N){
Q.push(i);
inQ[i] = true;
cnt[i]++;
}
bool negCycle = false;
while(!Q.empty() && !negCycle){
int cur = Q.front(); Q.pop();
inQ[cur] = false;
for(auto [nxt, w]: links[cur]){
if(dist[nxt] <= dist[cur] + w) continue;
dist[nxt] = dist[cur] + w;
if(!inQ[nxt]){
Q.push(nxt);
inQ[nxt] = true;
cnt[nxt]++;
if(cnt[nxt] >= N){
negCycle = true;
break;
}
}
}
}
if(negCycle) cout << "YES\n";
else cout << "NO\n";
}