[백준]지름길(1446)

문제 링크 : [백준]지름길(1446)

문제 설명

고속도로를 D지점까지 이동해야 합니다.
N개의 지름길이 존재하며, 지름길은 S_i지점에서 들어가 E_i지점에서 나오게 되고, D_i만큼의 거리를 가게 됩니다.
이때, D지점까지가는 최단 이동거리를 구하세요.

입력

N(지름길 갯수, 1 <= N <= 12)
D(도착지점, 0 <= M <= 10,000)
S_i E_i D_i(시작 지점, 도착 도시, 지름길의 길이, 0 <= D_i <= 10,000)

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

출력

70

카테고리

#다익스트라

시간 복잡도 상한

O(N² * D)

해결 방법

1. 엣지에 대한 정보가 굉장히 애매해보입니다.
2. 모든 지름길간에 도착지점이 출발지점보다 작거나 같은 경우, 엣지 정보들을 만들어주어야 합니다.
3. 그래서 우선순위 큐에 정보를 넣을 때, 비용은 [현재까지 오는 비용 + 지름길 비용 + (지름길 시작 지점 - 현재 도착지점)]이 됩니다.
4. 시작위치 0, 비용 0에서 시작하여, 3번 작업을 반복하면서 D지점에 도착할 때까지 다익스트라를 돌리면 됩니다.
5. 단, 지름길 정보 중 도착지까지 가는 경우가 없을 수 있으니, 지름길 정보에 {출발지점 : D, 도착지점 : D, 비용 0}인 엣지 정보를 강제로 넣어줍니다.

시간복잡도

O(N² * log(N²))

코드

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>P;
int n,m,d[13][3],i;
priority_queue<P,vector<P>,greater<P>>q;
int main(){
    scanf("%d%d",&n,&m);
    for(;i<n;i++)scanf("%d%d%d",d[i],d[i]+1,d[i]+2);
    d[n][0]=d[n][1]=m;
    q.push({0,0});
    while(!q.empty()){
        P c=q.top();q.pop();
        if(c.second==m){
            printf("%d",c.first);
            break;
        }
        for(i=0;i<=n;i++)if(d[i][0]>=c.second)q.push({d[i][2]+d[i][0]-c.second+c.first,d[i][1]});
    }
}