@fuheimao 2015-09-05T13:00:45.000000Z 字数 2756 阅读 782

# Revamping Trails

## BZOJSolution腹黑猫

Farmer John dutifully checks on the cows every day. He traverses some of the M(1M50,000)$M (1 ≤ M ≤ 50,000)$ trails conveniently numbered 1..M$1..M$ from pasture 1$1$ all the way out to pasture N$N$ (a journey which is always possible for trail maps given in the test data). The N(1N10,000)$N (1 ≤ N ≤ 10,000)$ pastures conveniently numbered 1..N$1..N$ on Farmer John's farm are currently connected by bidirectional dirt trails. Each trail i$i$ connects pastures P1i$P1_i$ and P2i(1P1iN;1P2iN)$P2_i (1 ≤ P1_i ≤ N; 1 ≤ P2_i ≤ N)$ and requires Ti(1Ti1,000,000)$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(1K20)$K (1 ≤ K ≤ 20)$ trails to turn into highways, which will effectively reduce the trail's traversal time to 0$0$. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1$1$ to N$N$.

Input

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

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

Sample Input

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

1. 保存上次求出的最短距离数组
2. 若上层图中，有边<u,v>$$,则连一条从图Gi1$G_{i-1}$中的u$u$到图Gi$G_i$中的v$v$的边，权值为0，代码实现很巧妙
3. Dijkstra求本层最短路
#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;}