Floyd_Warshall

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/33527 🧐 관찰 및 접근 # 뭔가 전반적으로 세팅이 BOJ 5214 환승이 생각나는 것 같기도? 나이브하게 돈다면, 각 노선에 있을 수 있는 최대 정류장 수가 10만개니까, 이걸 다 돌기 시작하면 상당히 막막해진다. 그림을 그려서 어떤 상황인지 더 잘 판단해보자. ![[Drawing 2026-02-17 14.06.51.excalidraw.png]] 일단 예제 1번은 이런데, 흠. 확실히 정류장보단 노선 단위로 어떻게 잘 보고싶긴 하다. 노선은 총 $5 \times X = 500$개이다. 이때, 노선의 환승 각 정류장 $N$개마다 $\binom{5}{2}$ 개이므로 최대 $100\,000 \times = 1\,000\,000$개인 것 같다. 중복도 제거할수도 있고. 아? 이게 노선이 충분히 적으니, 플로이드 워셜이 가능해보인다. 쿼리는 정점에 대해 들어오니, $U_i, V_i$가 각각 5개 노선에 속하는 경우 25가지에 대해 노선으로 계산하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, X; cin >> N >> X; vector<array<int, 5>> bus(N); rep(i, 0, N) rep(j, 0, 5) cin >> bus[i][j]; auto toIdx = [&](pii p){ return p.first*X + (p.second - 1); }; vector<vector<int>> dist(5*X, vector<int>(5*X, 1e9)); rep(i, 0, 5*X) dist[i][i] = 0; rep(i, 0, N) rep(j, 0, 5) rep(k, j+1, 5){ int u = toIdx({j, bus[i][j]}), v = toIdx({k, bus[i][k]}); dist[u][v] = dist[v][u] = 1; } rep(k, 0, 5*X) rep(i, 0, 5*X) rep(j, 0, 5*X) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; int ans = 1e9; rep(i, 0, 5) rep(j, 0, 5){ int idx_u = toIdx({i, bus[u-1][i]}), idx_v = toIdx({j, bus[v-1][j]}); ans = min(ans, dist[idx_u][idx_v]); } cout << (ans == 1e9 ? -1 : ans+1) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/21940 🧐 관찰 및 접근 # 일단 가중치가 있는 방향 그래프인데.. 어떤 도시 $X$에 대해 준형이와 친구들이 살고있는 모든 도시에 대해 왕복 시간을 구할 수 있을까? $N$이 충분히 작으므로, 플로이드 워셜을 사용해서 모든 도시간의 이동시간을 구할 수 있겠다. 이후에는 모든 도시 $X$에 대해 $K$번의 계산으로 왕복시간들의 최댓값을 구할 수 있다. 시간복잡도 $O(N^3 + NK)$로 풀릴 것 같다! 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; rep(i, 0, N) rep(j, 0, N) cost[i][j] = 1e15; rep(i, 0, N) cost[i][i] = 0; rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; u--; v--; 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]); cin >> K; vector<int> v(K), ans; rep(i, 0, K) cin >> v[i]; ll mn = 1e15; rep(X, 0, N){ ll tmp = 0; for(auto c: v) tmp = max(tmp, cost[X][c-1] + cost[c-1][X]); if(tmp < mn){ mn = tmp; ans.clear(); } if(tmp == mn) ans.push_back(X+1); } for(auto c: ans) cout << c << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: 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"; } 🔒 구현 코드 잠금