[PS] 백준 9370번: 미확인 도착지

|

문제

내가 이해한 문제 내용

지나가야 할 특정 경로, 출발지, 목적지 후보가 주어질 때, 특정 경로를 지나서 목적지 후보에 도착하는 최단 경로 중 실제 최단 경로와 같은 값을 오름차순으로 구하여라.

접근 방식

  • 다익스트라를 통해 출발지 $s$로부터의 최단경로를 구한다.
  • 다익스트라를 통해 특정경로의 한쪽 정점인 $g$로부터의 최단경로를 구한다.
  • 다익스트라를 통해 특정경로의 한쪽 정점인 $h$로부터의 최단경로를 구한다.
  • 이렇게 구한 후 2가지 경우가 존재한다.
    • $s$로부터 $g$까지의 최단경로 가중치 + $g$와 $h$ 사이의 경로 가중치 + $h$로부터 목적지까지의 경로 가중치
    • $s$로부터 $h$까지의 최단경로 가중치 + $h$와 $g$ 사이의 경로 가중치 + $g$로부터 목적지까지의 경로 가중치
  • 각 목적지 후보들에 대해 위의 2가지 경우를 계산해서 작은 값을 구하고 그 작은 값과 실제 최단경로의 가중치와 비교해서 같을 때만 답에 추가해주면된다.
  • 답을 오름차순 정렬한 뒤 출력한다.

어려웠던 점 & 배운 점

  • 다익스트라를 까먹었다가 간신히 기억해냈다;;
  • TC 여러개인 경우라면 초기화 할 때 실수가 있을 수 있으니 지역변수로 선언하는 것이 좋다.

시간복잡도

  • 다익스트라: $O(mlog_2{n})$
  • 정렬: $O(tlog_2{t})$
  • 최종: $O(mlog_2{n})$

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;

int tc,n,m,t,s,g,h,a,b,d,p;
int sps[2001],spg[2001],sph[2001],vi[2001];
const int INF = 2e9;
priority_queue<pii,vector<pii>,greater<pii>> pq;

void dijk(pii src, int *sp, vector<pii> *graph)
{
    for(int i=1; i<=n; i++) {
        sp[i] = INF;
        vi[i] = 0;
    }
    sp[src.second] = 0;
    pq.push(src);

    while(!pq.empty()) {
        pii v = pq.top(); pq.pop();
        vi[v.second] = 1;
        for(int i=0; i<graph[v.second].size(); i++){
            int next = graph[v.second][i].second;
            if(!vi[next] && sp[v.second]+graph[v.second][i].first < sp[next]){
                sp[next] = sp[v.second]+graph[v.second][i].first;
                pq.push({sp[next],next});
            }
        }
    }
}

int main(void)
{
    scanf("%d",&tc);

    while(tc--) {
        vector<pii> graph[2001];
        vector<int> candidate,ans;

        scanf("%d%d%d",&n,&m,&t);
        scanf("%d%d%d",&s,&g,&h);

        for(int i=0; i<m; i++){
            scanf("%d%d%d",&a,&b,&d);
            graph[a].push_back({d,b});
            graph[b].push_back({d,a});
            if((a==g && b==h)||(a==h && b==g)) p = d;
        }
        candidate.resize(t);
        for(int i=0; i<t; i++){
            scanf("%d",&candidate[i]);
        }

        dijk({0,s},sps,graph);
        dijk({0,g},spg,graph);
        dijk({0,h},sph,graph);

        for(int i=0; i<candidate.size(); i++){
            int org = sps[candidate[i]];
            int firstPath1 = sps[g];
            int firstPath2 = sps[h];
            int secondPath1 = sph[candidate[i]];
            int secondPath2 = spg[candidate[i]];
            int path1 = firstPath1+p+secondPath1;
            int path2 = firstPath2+p+secondPath2;
            int path = path1<path2?path1:path2;

            if(org==path) ans.push_back(candidate[i]);
        }
        sort(ans.begin(),ans.end());
        for(auto vertex : ans) printf("%d ",vertex);
        
        puts("");
    }

    return 0;
}