[1162] 도로포장

### Dijkstra ###

[1162] 도로포장 : http://boj.kr/1162

<소스코드>

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 1e9;
 
typedef pair<int, int> P;
typedef pair<int, P> K;
 
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
 
    vector<P> g[10001];
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(P(b, c));
        g[b].push_back(P(a, c));
    }
 
    vector<vector<int> > dist(k+1, vector<int>(n+1, INF)); 
    dist[k][1] = 0; // kth pave, cur vertex
 
    priority_queue<K> pq;
    pq.push(K(0, P(1, k))); // dist, v, k
 
    bool visited[21][10001]={0}; 
  
    while(!pq.empty()) {
        int curV, curK;
        do {
            curV = pq.top().second.first;
            curK = pq.top().second.second; 
            pq.pop();
        } while(!pq.empty() && visited[curK][curV]);
  
        if(visited[curK][curV]) break;
        visited[curK][curV] = 1;
 
        for(auto &p : g[curV]) {
            int nextV = p.first;
            int d = p.second;
            
            if(dist[curK][nextV] > dist[curK][curV] + d) {
                dist[curK][nextV] = dist[curK][curV] + d;
                pq.push(K(-dist[curK][nextV], P(nextV, curK)));
            }
            if(curK-1 >= 0 && dist[curK-1][nextV] > dist[curK][curV]) {
                dist[curK-1][nextV] = dist[curK][curV];
                pq.push(K(-dist[curK-1][nextV], P(nextV, curK-1)));
            }
        }
    }
    
    int ans = 1e9;
    for(int i=0; i<=k; i++) {
        ans = min(ans, dist[i][n]);
    }
    
    printf("%d\n", ans);
    return 0;
}
 

>> dist[k][i] : 포장을 k개 할 수 있는 상태에서 시작정점에서 i번 정점까지의 최단거리, 

    k값의 변화가 없는 겨우, 우리가 지금까지 구했던 다익스트라 dist 배열이다.