ShortestPathWithMagic

Graph, Shortest Path, Dijkstra


출처: TopCoder ShortestPathWithMagic

SOL)

k >= 1 일때, 새로운 점을 만들어 준다.
예를들어 0번 정점은 50이라는 다른 정점도 갖게 된다.
그리고 50이상의 정점으로 가는 간선을 이용할 때는
기존의 값에 2를 나눠준다. 이렇게 최단 경로를 구하고
res[1], res[51]중 작은 것을 선택하면 된다.

[-] Collapse

#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
class ShortestPathWithMagic{
private:
    int edge[110][110];
    vector<int> res;
    int p;
    int n;
public:
    double getTime(vector <string> dist, int k){
        p = k;
        n = dist.size();

        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                edge[i][j] = ((int)dist[i][j]-48) * 10;
                edge[i][j + 50] = edge[j + 50][i] = edge[i][j];
                edge[i + 50][j + 50] = edge[j + 50][i + 50] = edge[i][j];
            }
        }
        dijkstra();

        return min(1.*res[1] / 10, 1.*res[51] / 10);
    }
    void dijkstra(){
        res = vector<int>(110, (1 << 30));
        priority_queue<pair<int, pair<int, int> > >pq;//weight, k, here;
        res[0] = 0;
        pq.push(make_pair(0, make_pair(0, 0)));
        while (!pq.empty()){
            int here = pq.top().second.second;
            int cost = -pq.top().first;
            int c = pq.top().second.first;
            pq.pop();
            if (res[here] < cost) continue;
            for (int i = 0; i < n; i++){
                if (here == i || here - 50 == i) continue;
                int nextDist = cost + edge[here][i];
                if (nextDist < res[i]){
                    res[i] = nextDist;
                    pq.push(make_pair(-nextDist, make_pair(c, i)));
                }
            }
            for (int i = 50; i < n+50; i++){
                if (here == i || here + 50 == i) continue;
                int nextDist = cost + edge[here][i]/2;
                if (nextDist < res[i] && c+1 <= p){
                    res[i] = nextDist;
                    pq.push(make_pair(-nextDist, make_pair(c+1, i)));
                }
            }
        }
    }
};
/*
int main(){
    vector<string> vec;
    vec.push_back("094");
    vec.push_back("904");
    vec.push_back("440");

    ShortestPathWithMagic test;
    cout << test.getTime(vec, 1) << endl;
}*/