BOJ 5719: 거의 최단 경로

https://www.acmicpc.net/problem/5719

  • 3월동안 210문제 풀기 (11/210)
  • 단순히 Parent 배열만으로는 Dijkstra의 최단경로를 못찾음
  • Tree의 인접배열을 다시 만드는 식으로 해야함
  • 배열의 원소를 저장하는것은 위험함. 그냥
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#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);
  }
}