[백준]간선 이어가기 2(14284)

문제 링크 : [백준]간선 이어가기 2(14284)

문제 설명

연결이 없는 노드 N개가 주어집니다.
그 이후에 M개의 무방향 가중치 엣지가 주어집니다.
출발지 S와 도착지 T가 주어지면, 이전에 주어진 간선들의 순서를 원하는대로 바꾸고 순서대로 하나씩 간선을 이어나가다가 S와 T가 이어지는 순간 작업을 멈춥니다.
이때 이은 간선들의 가중치의 합의 최소값을 구하세요.

입력

N(노드의 갯수, 1 <= N <= 5,000)
M(엣지의 갯수, 1 <= M <= 100,000)
A_i B_i C_i(출발 노드, 도착 노드, 가중치, 1 <= C_i <= 100)

8 9
1 2 3
1 3 2
1 4 4
2 5 2
3 6 1
4 7 3
5 8 6
6 8 2
7 8 7
1 8

출력

5

카테고리

#다익스트라

시간 복잡도 상한

O(N²) 혹은 O(M * logM)

해결 방법

1. 간선의 순서를 마음대로 조작하여 순서대로 엣지들을 잇는다는 것은 바꾸어 말하면 주어진 간선 중 원하는 것만 고른다는 것과 같습니다.
2. 그리고 시작점에서 도착점까지 이어지는 순간까지 이은 간선들의 가중치의 최소값이라는 것은 최단거리와 같습니다.
3. 즉 다익스트라를 이용하여 최단거리를 구하면 됩니다.

시간복잡도

O(M * logM)

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define N 5001
using namespace std;
typedef pair<int,int>P;
int n,m,a,b,c,d[N];
vector<P>v[N];
priority_queue<P,vector<P>,greater<P>>q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    cin>>a>>b;
    q.push({0,a});
    while(!q.empty()){
        P x=q.top();q.pop();
        if(d[x.second])continue;
        d[x.second]=1;
        if(x.second==b){
            cout<<x.first;
            break;
        }
        for(P y:v[x.second])if(!d[y.second])q.push({x.first+y.first,y.second});
    }
}