BOJ 1504

특정한 최단 경로 성공

 

 

1 초

256 MB

55090

13810

9328

24.562%

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1 복사

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 복사

7​

최단거리 문제이다.

1 -> v1 -> v2 -> N, 1 -> v2 -> v1 -> N 중 최솟값이 답이 된다는 것은 금방 이해되는데, 플로이드로는 왜 계속 틀리는지 이해가 잘 안간다.

이동했던 간선을 다시 지나는 경우는 case1에서는 v2에서 N을 못가는 경우에만 해당하는게 아닌가, 그렇다면 그런 경우에는 플로이드 경우의 최단거리가 INF가 되므로 INF일 경우에 다시 체크해줘서 1 -> v1 -> v2 -> v1 -> N이 되고, 이 경우는 결국  

1 -> v2 -> v1 -> N이 되는데 , 이러면 플로이드를 사용해도 될거같은데 잘 모르겠다.

다익스트라 3번돌려서 풀었다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int N, E, v1, v2, ans;
vector<vector<pair<int,int>>>graph(1000);

int dijstra(int start, int last){
    vector<int>dist(N+1, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while(!pq.empty()){
        int cur_dist = pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();
        for(int i=0; i<graph[cur_node].size(); i++){
            int nxt_node = graph[cur_node][i].first;
            int nxt_dist = cur_dist + graph[cur_node][i].second;
            if(nxt_dist < dist[nxt_node]){
                dist[nxt_node] = nxt_dist;
                pq.push({nxt_dist, nxt_node});
            }
        }
    }
    // for(int i=1; i<=N; i++){
    //     cout<<dist[i]<<' ';
    // }
    return dist[last];
}

int main(){
    cin>>N>>E;
    for(int i=0; i<E; i++){
        int a, b, c;
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    cin>>v1>>v2;
    ans = min(dijstra(1,v1)+dijstra(v1,v2)+dijstra(v2,N),dijstra(1,v2)+dijstra(v1,v2)+dijstra(v1,N) );
    // cout<<dijstra(1,v2)<<' '<<dijstra(v1,v2)<<' '<<dijstra(v1,N)<<endl;
    if(ans >= INF || ans <= 0) cout<<-1;
    else cout<<ans;
}