Dijkstra

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32655 🧐 관찰 및 접근 # 시작 정점에서 각 출구로 갈 수 있는 최단 경로를 구한 후, 열리는 타이밍에 맞춰 나갈 수 있는 최소 시간을 구하자. $KX$초 단위로 출구가 도는게 로테이션 돌고, 이분탐색으로 그 타이밍을 찾은 후 그 블럭에서 나갈 수 있는지, 그 다음블럭에서 나갈 수 있는지 체크하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } vector<ll> dist(N+1, LLONG_MAX); priority_queue<pll, vector<pll>, greater<pll>> pq; dist[1] = 0; pq.push({0, 1}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(dist[cur] < cd) continue; for(auto [nxt, w]: links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23807 🧐 관찰 및 접근 # 무향그래프고, 정해진 정점중 세개 이상의 정점을 지나야 한다.. 이걸 경로로 나타내면 $X \rightarrow P_i \rightarrow P_j \rightarrow P_k \rightarrow Z$이 될 것이다. 이때, $X$에서 시작한 경로와 $Z$에서 시작한 최단 경로는 다익스트라로 쉽게 계산할 수 있다. 이제 가운데 $P_j$에서 시작한 최단 경로를 구해서, 각 $P_i, P_k$에 대해 구하면 되겠다. $O(V+E)$의 다익스트라를 $P \leq 100$번 돌려야 한다. 조금 무거운 4천만정도일거같은데, 6초제한이니 잘 돌것같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M; cin >> N >> M; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int X, Z; cin >> X >> Z; vector<ll> dist_fromX(N+1, 1e18), dist_fromZ(N+1, 1e18); auto dijkstra = [&](ll start, vector<ll> &dist){ priority_queue<pll, vector<pll>, greater<pll>> pq; dist[start] = 0; pq.push({0, start}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(cd > dist[cur]) continue; for(auto [nxt, w] : links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } }; dijkstra(X, dist_fromX); dijkstra(Z, dist_fromZ); int P; cin >> P; vector<int> cand(P); rep(i, 0, P) cin >> cand[i]; ll ans = 1e18; for(int c2: cand){ vector<ll> dist_fromC(N+1, 1e18); dijkstra(c2, dist_fromC); for(int c1: cand) for(int c3: cand){ if(c1 == c2 || c2 == c3 || c1 == c3) continue; ans = min(ans, dist_fromX[c1] + dist_fromC[c1] + dist_fromC[c3] + dist_fromZ[c3]); } } if(ans >= 1e18) ans = -1; cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1504 🧐 관찰 및 접근 # $a$에서 $b$까지 가되, $v_1, v_2$를 무조건 지니야 한다. 이는 $a \rightarrow v_1 \rightarrow v_2 \rightarrow b$ 혹은 $a \rightarrow v_2 \rightarrow v_1 \rightarrow b$ 두가지중 하나이지 않을까? 각 움직임에 대해 나이브하게 다익스트라를 수행해도 6번밖에 안되므로, 그냥 돌리자. 경로가 없을 수 있음에 유의하자. 💻 풀이 # 코드 (C++): int N, E; vector<pii> links[810]; int get_dist(int s, int e){ vector<int> dist(N+1, 1e9); priority_queue<pii, vector<pii>, greater<pii>> pq; dist[s] = 0; pq.push({0, s}); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if(dist[u] < d) continue; if(u == e) return d; for(auto [v, w]: links[u]){ if(dist[v] > d+w){ dist[v] = d+w; pq.push({dist[v], v}); } } } return 1e8; } void solve(){ cin >> N >> E; rep(i, 0, E){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int v1, v2; cin >> v1 >> v2; int ans = min(get_dist(1, v1) + get_dist(v1, v2) + get_dist(v2, N), get_dist(1, v2) + get_dist(v2, v1) + get_dist(v1, N)); if(ans >= 1e8) cout << -1; else cout << ans; } 🔒 구현 코드 잠금