(c++) 다익스트라 9370번: 미확인 도착지

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

9370번: 미확인 도착지

 

 

---

 

 

9370번: 미확인 도착지

 

다익스트라 : 우선 순위 큐  네 번째 문제이다.

 

앞선 문제와 마찬가지로 기본 알고리즘에서 거의 건들지 않고, 입력 부분만 생각하면 된다.

 

시작점이 주어지고, 도착점은 여러 개이고, 

 

도착점의 최단 경로가 주어지는 정점 사이의 간선을 포함할 경우만 출력하면 된다.

 

다익스트라는 두 번 실행하는데

 

1번 째는 시작점에서 다익스트라를 실행하고

 

2번 째는 지나가야 하는 정점 두 개 중 하나를 선택해서 진행한다.

 

---

 

풀이

 

1. 시작점에서 지나는 정점 중 하나까지의 거리 + 그 정점에서의 도착점까지의 최단 거리

 

2. 시작점에서 도착점까지의 최단 거리

 

g, h가 반드시 지나가야 하는 간선 사이의 정점이라면

 

1번 경우는 출발점 다익스트라 결과에서 g, h 둘 중 가까운 것을 선택한 후

 

만일 g를 선택하였으면 그 다음 다익스트라는 h를 선택한다.

 

h 다익스트라에서는 h → 도착점의 결과를 저장해둔다.

 

즉 1번 경우는 출발점 → g/h → (g 선택 시) h/ (h 선택 시) g → 도착점

 

2번은 출발점 다익스트라에서 도착점까지의 최단 거리이다.

 

2번 경우는  출발점 → 도착점

 

위 두 경우가 같다면 정답 처리를 하였다.

 

 

런타임 오류 중 outofBounds는 (16퍼센트)

 

코드에서 벡터의 크기 설정이나 반복문의 설정을 꼼꼼히 해주어야 오류가 나지 않는다.

 

---

 

코드

 

#include <bits/stdc++.h>
#define INF 50000000
using namespace std;

//정점 수
int n;

vector<pair<int, int> > graph[2001];

vector<int> dijkstra(int start) {
    vector<int> dist(n+1, INF);
    dist[start] = 0;
    // 가중치, 정점 순서
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, start));
    while(!pq.empty()) {
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if (dist[here] < cost) continue;
        for (int i = 0; i < graph[here].size(); i++) {
            int there = graph[here][i].first;
            int nextDist = cost + graph[here][i].second;
            if (dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    return dist;
}

int main (void) {
    // 테스트 케이스 수
    int num;
    cin >> num;
    for (int i = 0; i < num; i++) {
        // n = 정점, m = 간선, t = 목적지후보 수
        int m, t;
        cin >> n >> m >> t;
        for (int i = 1; i <= n; i++) {
            //vector<pair<int, int> >().swap(graph[i]);
            graph[i].clear();
        }
        // s = 출발지, g-h = 지나간 간선
        int s, g, h;
        cin >> s >> g >> h;
        int dist_gh; 
        for (int i = 0; i < m; i++) {
            int a, b, d;
            cin >> a >> b >> d;
            graph[a].push_back({b, d});
            graph[b].push_back({a, d});
            if ((a == g && b == h) || (a == h && b == g)) {
                dist_gh = d;
            }
        }
        // 목적지 후보 저장 벡터
        vector<int> end_t;
        for (int j = 0; j < t; j++) {
            int temp;
            cin >> temp;
            end_t.push_back(temp);
        }
        sort(end_t.begin(), end_t.end());
        // 다익스트라 두 번의 결과 저장
        vector<int> f_dist(n+1, INF);
        vector<int> s_dist(n+1, INF);
        f_dist = dijkstra(s);
        // 출발지 + g or h + g-h 거리
        int dist_sum;
        if (f_dist[g] <= f_dist[h]) {
            s_dist = dijkstra(h);
            dist_sum = f_dist[g] + dist_gh;
        } else {
            s_dist = dijkstra(g);
            dist_sum = f_dist[h] + dist_gh;
        }
        for (int k = 0; k < end_t.size(); k++) {
            int node_t = end_t[k];
            int dist_t = f_dist[node_t];
            if (dist_t != INF) {
                long long total = dist_sum + s_dist[node_t];
                if (total != INF &&  dist_t == total) {
                    cout << node_t << " ";
                } else continue;
            }
        }
        cout << endl;
    }
}