[백준]도로포장(1162)

문제 링크 : [백준]도로포장(1162)

1162번: 도로포장

문제 설명

N개의 노드와 M개의 양방향 간선 정보가 주어집니다.

이 때, 1번 노드에서 N번 노드로 이동하는데, K개의 간선의 비용을 0으로 변경 할 수 있습니다.

1번 노드에서 N번 노드까지의 최단거리를 구하세요.

입력

N(노드의 갯수, 1 <= N <= 10,000)

M(간선의 갯수, 1 <= M <= 50,000)

K(포장할 도로의 갯수, 1 <= K <= 20)

A B C(A, B : 연결 노드 번호, C : 도로 길이, 1 <= C <= 1,000,000) 

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

 

출력

1

 

카테고리

#다익스트라 #DP

 

시간 복잡도 상한

O(N²)

 

해결 방법

1. 다익스트라 문제와 굉장히 비슷합니다.
2. 기본 다익스트라와 다른 것은 이동하면서 K개의 간선의 비용을 0으로 만들 수 있는 것입니다.
3. 단순 다익스트라로 풀 수 없는 이유는 한 번 큐에서 뽑힌 노드는 그 값이 고정되기 때문에, 이전에 몇개의 도로를 포장했는지에 상관없이 값이 고정됩니다.
4. 그렇다면 visited 배열을 노드 번호 뿐만 아니라 남은 도로 포장 갯수까지 보도록 하여 visited[N][K]의 형태로 만듭니다.
5. X노드까지 몇 개의 간선을 포장했는지 알고, 그 때의 최소 비용만 안다면 그 이후는 일반적인 다익스트라와 같아집니다.

시간복잡도

O(N+KMlogM)

코드

#include<cstdio>
#include<vector>
#include<queue>
#define pi pair<int,int>
#define pl pair<long long,int>
#define mp make_pair
using namespace std;
int n,m,k,a,b,c,d[10001][21],x,y;
long long s;
vector<pi>v[10001];
priority_queue<pl,vector<pl>,greater<pl>>q;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    while(m--)scanf("%d%d%d",&a,&b,&c),v[a].push_back(mp(b,c)),v[b].push_back(mp(a,c));
    q.push(mp(0,32|k));
    while(1){
        pl t=q.top();q.pop();
        s=t.first,x=t.second>>5;y=t.second&0x1f;
        if(d[x][y])continue;
        if(x==n){
            printf("%lld",s);
            break;
        }
        d[x][y]=1;
        for(a=0;a<v[x].size();a++){
            if(!d[v[x][a].first][y])q.push(mp(s+v[x][a].second,v[x][a].first<<5|y));
            if(y&&!d[v[x][a].first][y-1])q.push(mp(s,v[x][a].first<<5|(y-1)));
        }
    }
}