BOJ 5719: 거의 최단 경로 작성일 2020-03-04 https://www.acmicpc.net/problem/5719 3월동안 210문제 풀기 (11/210) 단순히 Parent 배열만으로는 Dijkstra의 최단경로를 못찾음 Tree의 인접배열을 다시 만드는 식으로 해야함 배열의 원소를 저장하는것은 위험함. 그냥 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include <bits/stdc++.h> using namespace std; struct Edge { int v, dist; }; struct Node { int u, dist; bool operator<(const Node& b) const { return dist > b.dist; } }; Edge* saveEdge[510][510]; struct Graph { int N, INF = 1e9; vector<vector<int>> parent; vector<vector<Edge*>> adj; vector<int> dist; Graph(int n): N(n), parent(n+1), adj(n+1) { memset(saveEdge, 0, sizeof(saveEdge)); } inline void addEdge(int u, int v, int dist) { Edge* newEdge = new Edge({v,dist}); adj[u].push_back(newEdge); saveEdge[u][v] = newEdge; } void dijkstra(int S) { dist = vector<int>(N+1, INF); priority_queue<Node> pq; pq.push({S, 0}); dist[S] = 0; while(pq.size()) { Node cur = pq.top(); pq.pop(); if(cur.dist != dist[cur.u]) continue; for(Edge* e: adj[cur.u]) { if(e->dist == -1) continue; if(dist[e->v] > cur.dist + e->dist) { parent[e->v].clear(); parent[e->v].push_back(cur.u); dist[e->v] = cur.dist + e->dist; pq.push({e->v, dist[e->v]}); } else if(dist[e->v] == cur.dist + e->dist) { parent[e->v].push_back(cur.u); } } } } void removeSSP(int D) { int cur = D; for(int par: parent[cur]) { saveEdge[par][cur]->dist = -1; removeSSP(par); } } }; int main() { int N = 1, M, S, D, U, V, P; while(1) { scanf("%d %d", &N, &M); if(N == 0 && M == 0) break; Graph graph(N); scanf("%d %d", &S, &D); for(int i = 0; i < M; i++) { scanf("%d %d %d", &U, &V, &P); graph.addEdge(U, V, P); } graph.dijkstra(S); graph.removeSSP(D); graph.dijkstra(S); int ssp = graph.dist[D]; printf("%d\n", ssp >= graph.INF ? -1 : ssp); } }