문제

문제 링크

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

예제

입력
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

출력
5
-1
6

나의 접근 방법

처음에 Union-Find를 활용하여 경로를 저장하려 했으나 경로가 여러개 존재할 수 있기 때문에 다른 방법을 찾아야 했다.
따라서 다익스트라가 갱신될 때마다 이전 경로를 vector에 저장했고, 이전 경로들을 저장한 vector를 참고하여 최단 경로들을 제거했다.
도착지 D에서 BFS를 돌린다고 했을 때 Dist[D] = Dist[prev] + inputs[prev] 인 점을 활용하여 최단 경로를 찾을 수 있다.
해당 부분의 코드는 다음과 같다.

for(int i = 0 ; i<trace[now].size() ; i++){
  int next = trace[now][i];
  if(inputs[next][now] && dist[next] == dist[now] - inputs[next][now]){
    inputs[next][now] = 0;
    q.push(next);
  }
}

코드

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
#include<cstring>
using namespace std;

int N,M,S,D;
vector<int> trace[501];
vector<vector<int>> inputs(501, vector<int>(501));
typedef pair<int, int> pii;

#define MAX 1000000000

struct info{
  int idx;
  int d;
};

struct cmp{
  bool operator()(info t, info u){
    return t.d > u.d;
  }
};

vector<int> dijkstra(){

  vector<int> dist(N, MAX);
  priority_queue<struct info, vector<struct info>, cmp> pq;
  dist[S] = 0;
  pq.push({S, 0});
  while(!pq.empty()){
    struct info now = pq.top();
    int nowIdx = now.idx, nowValue = now.d;
    pq.pop();
    for(int i = 0 ; i<N ; i++){
      int nextValue = inputs[nowIdx][i] + nowValue;
      if(!inputs[nowIdx][i]) continue;
      if(dist[i] < nextValue) continue;
      // 클 때만 pq에 넣는다.
      if(dist[i] > nextValue){
        pq.push({i, nextValue});
      }
      // 같을 때도 체크는 해야 하기 때문에 다음과 같이
      dist[i] = nextValue;
      trace[i].push_back(nowIdx);
    }
  }
  return dist;
}

int main(void){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  while(1){
    cin>>N>>M;
    if(N == 0 && M == 0) break;
    cin>>S>>D;

    // 사용하는 배열들 초기화
    for(int i = 0 ; i<N ; i++){
      trace[i].clear();
      for(int j = 0 ; j<N ; j++){
        inputs[i][j] = 0;
      }
    }

    for(int i = 0 ; i<M ; i++){
      int U,V,P;
      cin>>U>>V>>P;
      inputs[U][V] = P;
    }

    // 첫번째 다익스트라 돌려서 최단 경로 찾기
    vector<int> dist = dijkstra();
    queue<int> q;
    // BFS를 통해 최단 경로 제거해주기
    // 최단 경로인지 확인하는 방법은 5번에서 4번으로 간다고 했을 때 Dist[5] = Dist[4] + inputs[4][5] 인 것을 활용
    q.push(D);
    while(!q.empty()){
      int now = q.front();
      q.pop();
      for(int i = 0 ; i<trace[now].size() ; i++){
        int next = trace[now][i];
        if(inputs[next][now] && dist[next] == dist[now] - inputs[next][now]){
          inputs[next][now] = 0;
          q.push(next);
        }
      }
    }

    // 최단 경로에 들어가는 간선들을 제거 한 후 다시 다익스트라 돌리기
    vector<int> secondDist = dijkstra();

    int result = secondDist[D] == MAX ? -1 : secondDist[D];
    cout<<result<<'\n';
  }
  return 0;
}