[백준] 택배(1719)

문제 링크 : [백준] 택배(1719)

문제 설명

양방향 그래프가 주어지면, 각각의 노드에서 다른 노드로 최단거리로 이동하기 위해서 처음으로 이동해야 하는 노드를 구하여, N*N 행렬로 표시합니다.

입력

N(노드 수, 1<=N<=200)
M(간선 수, 1<=M<=10,000)
D_i(M개가 나옴,1<=D_i<=1,000)

6 10
1 2 2
1 3 1
2 4 5
2 5 3
2 6 7
3 4 4
3 5 6
3 6 7
4 6 4
5 6 2

출력

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

카테고리

#다익스트라

시간 복잡도 상한

O(N*M) 혹은 O(N * M * logM)까지 가능합니다.

해결 방법

1. 최단거리를 구하는 방법은 다익스트라나 플로이드 와샬을 사용할 수 있습니다.
2. 최초로 이동하는 노드를 저장해야하기 때문에 플로이드 와샬보다는 다익스트라를 사용하는 것이 좋아 보입니다.
3. 각 노드를 시작점으로 다익스트라를 돌리게 되면 O(N*MlogM)정도가 걸리므로, 200 * 10,000 * 14 = 28,000,000 정도가 걸리므로 시간은 충분합니다.
4. 다익스트라에서 Priority Queue에 넣을 때, 일반적으로, 도착점과 비용을 넣지만, 여기서는 최초 이동 노드도 같이 저장합니다.
5. 실제 비용은 중요하지 않으므로, 비용을 저장하지는 않고, 처음 노드를 방문 할 때, 최초 방문 노드만 저장합니다.
   5-1. Priority Queue의 특성 상, 특정 노드에 한번 방문한 이후에, 다시 그 노드를 방문하는 엣지가 Priority Queue에서 나온다고 하여도, 이전에 방문했던 비용보다 항상 같거나 크므로, 최소 비용이 변경되지 않음을 알 수 있습니다.

코드

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int>P;
int n,m,d[201][201],a,b,c,i;
priority_queue<pair<int,P>,vector<pair<int,P>>,greater<pair<int,P>>>q;
vector<P>v[201];
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    for(i=1;i<=n;i++){
        while(!q.empty())q.pop();
        for(P x:v[i])q.push({x.second,{x.first,x.first}});
        while(!q.empty()){
            pair<int,P> x=q.top();q.pop();
            if(d[i][x.second.first])continue;
            d[i][x.second.first]=x.second.second;
            for(P N:v[x.second.first]){
                if(d[i][N.first])continue;
                q.push({x.first+N.second,{N.first,x.second.second}});
            }
        }
    }
    for(a=1;a<=n;a++){
        for(b=1;b<=n;b++){
            if(a==b)printf("- ");
            else printf("%d ",d[a][b]);
        }
        printf("\n");
    }
}