[백준]무엇을 아느냐가 아니라 누구를 아느냐가 문제다(9694)

문제 링크 : [백준]무엇을 아느냐가 아니라 누구를 아느냐가 문제다(9694)

문제 설명

0번 노드에서 N-1번 노드까지의 최단거리를 가는 경로를 구하세요.

입력

T(테스트 케이스, 1 < T < 100)
N(엣지의 갯수, N <= 20)
M(노드의 갯수, M <= 20)
A_i B_i C_i(출발지, 도착지, 비용, 1 <= C_i <= 4)

2
7 5
0 1 2
1 3 4
0 2 1
0 4 3
3 2 3
3 4 4
2 4 1
3 5
0 1 2
1 3 4
4 2 1

출력

Case #1: 0 2 4
Case #2: -1

카테고리

#다익스트라

시간 복잡도 상한

엄청 커도 될거 같아요.

해결 방법

1. 최단거리는 다익스트라를 이용하여 풀 수 있습니다.
2. 그러나 여기서는 최단거리가 걸리는 이동 경로를 알고 싶어합니다.
3. 다익스트라를 돌면서 우선순위 큐에서 데이터를 꺼낼 때, 현재 도착 노드에 어느 노드에서 이동했는지를 저장합니다.
4. M-1번 노드에서 3.에서 만든 데이터를 가지고 역추적하여 경로를 찾습니다.

시간복잡도

O(N * logN)

코드

#include<cstdio>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
struct N{
    N(int c,int d,int b):c(c),d(d),b(b){}
    int c,d,b;
    bool operator<(const N&a)const {return c>a.c;}
};
typedef pair<int,int>P;
int t,c,n,m,u[20],w[20],x,y,z;
vector<P>v[20];
priority_queue<N>q;
int main(){
    scanf("%d",&t);
    for(c=1;c<=t;c++){
        for(n=0;n<20;n++)v[n].clear(),w[n]=0,u[n]=-1;
        scanf("%d%d",&m,&n);
        while(m--){
            scanf("%d%d%d",&x,&y,&z);
            v[x].push_back({z,y});
            v[y].push_back({z,x});
        }
        q.push(N(0,0,-1));
        while(!q.empty()){
            N g=q.top();q.pop();
            if(w[g.d])continue;
            w[g.d]=1;
            u[g.d]=g.b;
            for(P r:v[g.d])if(!w[r.second])q.push(N(g.c+r.first,r.second,g.d));
        }
        printf("Case #%d: ",c);
        m=n-1;x=0;
        if(u[m]<0)printf("-1\n");
        else{
            while(m){
                w[x++]=m;
                m=u[m];
            }
            for(w[x]=0;x>=0;x--)printf("%d ",w[x]);
            printf("\n");
        }
    }
}