[5917] 거의 최단경로

### Dijkstra ###

[5917] 거의 최단경로 : http://boj.kr/5917

<소스코드>

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, s, e;
const int INF=1e9;
typedef pair<int, int> P;
 
vector<int> from[501];
 
void remove(vector<int> *from, int path[][501], int next)
{
    if(next == s) return ; 
 
    for(int i=0; i<from[next].size(); i++) {
        int cur = from[next][i];
        path[cur][next] = INF;
        remove(from, path, cur);
    }
 
}
 
int dijkstra(vector<P> *g, int path[][501])
{
    priority_queue<P> pq;
    pq.push(P(0, s));
 
    vector<int> dist(n+1, INF);
    dist[s] = 0;
 
    vector<bool> visited(n+1, 0);
 
    while(!pq.empty()) {
        int cur;
        do {
            cur = pq.top().second;
            pq.pop();
        } while(!pq.empty() && visited[cur]);
 
        if(visited[cur]) break;
 
        visited[cur] = 1;
 
        for(auto &p : g[cur]) {
            int next = p.first;
            int d = path[cur][next];
 
            if(dist[cur] + d == dist[next]) {
                from[next].push_back(cur);
            }
            else if(dist[next] > dist[cur] + d) {
                dist[next] = dist[cur] + d;
                pq.push(P(-dist[next], next));
                from[next].clear();
                from[next].push_back(cur);
            }
        }
    }
 
    return dist[e];    
}
 
int main()
{
    while(1) {
        scanf("%d%d", &n, &m);
        if(n == 0 && m == 0) break;
 
        scanf("%d%d", &s, &e);
 
        vector<P> g[501];
        int path[501][501]={0};
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(P(b, c));
            path[a][b] = c;
        }
 
        for(int i=0; i<n; i++)
            from[i].clear();
       
        int ans = dijkstra(g, path);
        if(ans == INF) {
            puts("-1");
            continue;
        }
        remove(from, path, e);
           
        ans = dijkstra(g, path);
        if(ans == INF) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}
 

>> 푸는데 참 오래 걸렸다.

>> 결론적으로 다익스트라 두번 돌렸으며, 처음 돌릴때, from 벡터배열에 한 정점까지의 최단경로에 대한 이전 정점들에 대해 기록을 해두고,

>> remove 로 삭제. 그리고 다시 다익스트라를 한번 돌리면 된다. 

>> 주의할 것이 두가지 있었다. 처음 다익스트라를 돌렸을때 처음부터 갈수 없는 경로가 존재하는 경우에 대해 처리하는 것과

>> 다음으론 k 번 정점까지의 최단거리로 오는 방법이 한가지 가 아닌경우, 그 모든 경우에 대한 간선을 제거하는 것.!!

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
5 3
0 4
0 1 1
0 2 1
0 3 1
5 6
0 4
0 1 10
0 2 1
2 1 2
1 3 1
3 4 2
1 4 5
6 8 
0 5
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 2 2
2 5 10
0 5 5
0 0
 

위 테스트 케이스에 대해 아래와 같이 정답이 나와야 한다.

마지막 테스트 케이스가 12가 나오면 여러가지 길이 있을 때, 한가지 길만 제거해서 생긴거라고 생각하면 된다.

5

-1

6

-1

15

-1