Revamping Trails

BZOJ Solution 腹黑猫

Farmer John dutifully checks on the cows every day. He traverses some of the $M (1 ≤ M ≤ 50,000)$ trails conveniently numbered $1..M$ from pasture $1$ all the way out to pasture $N$ (a journey which is always possible for trail maps given in the test data). The $N (1 ≤ N ≤ 10,000)$ pastures conveniently numbered $1..N$ on Farmer John's farm are currently connected by bidirectional dirt trails. Each trail $i$ connects pastures $P1_i$ and $P2_i (1 ≤ P1_i ≤ N; 1 ≤ P2_i ≤ N)$ and requires $T_i (1 ≤ T_i ≤ 1,000,000)$ units of time to traverse.

He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose $K (1 ≤ K ≤ 20)$ trails to turn into highways, which will effectively reduce the trail's traversal time to $0$. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture $1$ to $N$.

Input

• Line $1$: Three space-separated integers: $N$, $M$, and $K$

• Lines $2..M+1$: Line $i+1$ describes trail $i$ with three space-separated integers: $P1_i, P2_i$, and $T_i$
  Output

• Line $1$: The length of the shortest path after revamping no more than $K$ edges

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
Sample Output

题目大意就是求使$K$条边的权值为$0$后的最短路。
很神奇的一道题，认识了分层图。
我们把原图$G_0$复制$K$次，分别记为$G_1..G_k$。
在对原图$G_0$求完最短路后，
对于图$G_i(i∈[1,k])$，执行以下操作：

1. 保存上次求出的最短距离数组
2. 若上层图中，有边$<u, v>$,则连一条从图$G_{i-1}$中的$u$到图$G_i$中的$v$的边，权值为0，代码实现很巧妙
3. Dijkstra求本层最短路
4. Answer与本层求出的最短路相比，取最小值

#include "algorithm"
#include "iostream"
#include "queue"
#include "vector"
#include "cstring"
using namespace std;
struct Edge{
    int To;
    int Value;
};
struct Node{
    int Label;
    int Dis;
    bool operator < (const Node& b) const{
        return Dis > b.Dis;
    }
};
vector<Edge> Graph[10005];
int n, m, k;
long long Distant[10005][2];
bool Visited[10005];
void Dijkstra(bool X){
    memset(Visited, 0, sizeof(Visited));
    priority_queue<Node> Q;
    for (int i = 1; i <= n; ++i){
        Q.push((Node){i, Distant[i][X]});
    }
    for (int i = 1; i <= n; ++i){
        while (Q.size() && Visited[Q.top().Label]) Q.pop();
        if (Q.empty()) break;
        Node Now = Q.top();
        Q.pop();
        Visited[Now.Label] = true;
        for (vector<Edge>::iterator j = Graph[Now.Label].begin(); j != Graph[Now.Label].end(); ++j){
            if (!Visited[j -> To] && Distant[j -> To][X] > Distant[Now.Label][X] + j -> Value){
                Distant[j -> To][X] = Distant[Now.Label][X] + j -> Value;
                Q.push((Node){j -> To, Distant[j -> To][X]});
            }
        }
    }
}
int main(int argc, char const *argv[]){
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i){
        int P1, P2, T;
        cin >> P1 >> P2 >> T;
        Graph[P1].push_back((Edge){P2, T});
        Graph[P2].push_back((Edge){P1, T});
    }
    int Now = 0, Last = 1;
    memset(Distant, 0x3f, sizeof(Distant));
    Distant[1][Now] = 0;
    Visited[1] = true;
    Dijkstra(Now);
    long long Ans = Distant[n][Now];
    while (k--){
        Now ^= 1;
        Last ^= 1;
        //通过 Now 和 Last 实现巧妙的保存上次的距离数组
        for (int i = 1; i <= n; ++i){
            Distant[i][Now] = Distant[i][Last];
        }
        //连边
        for (int i = 1; i <= n; ++i){
            for (vector<Edge>::iterator j = Graph[i].begin(); j != Graph[i].end(); ++j){
                Distant[j -> To][Now] = min(Distant[j -> To][Now], Distant[i][Last]);
            }
        }
        Dijkstra(Now);
        Ans = min(Ans, Distant[n][Now]);
    }
    cout << Ans;
    return 0;
}