[关闭]
@fuheimao 2015-09-05T13:00:45.000000Z 字数 2756 阅读 74

Revamping Trails

BZOJ Solution 腹黑猫

Farmer John dutifully checks on the cows every day. He traverses some of the M(1M50,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(1N10,000) pastures conveniently numbered 1..N on Farmer John's farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1i and P2i(1P1iN;1P2iN) and requires Ti(1Ti1,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) 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

Sample Input

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

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

  1. 保存上次求出的最短距离数组
  2. 若上层图中,有边<u,v>,则连一条从图Gi1中的u到图Gi中的v的边,权值为0,代码实现很巧妙
  3. Dijkstra求本层最短路
  4. Answer与本层求出的最短路相比,取最小值
  1. #include "algorithm"
  2. #include "iostream"
  3. #include "queue"
  4. #include "vector"
  5. #include "cstring"
  6. using namespace std;
  7. struct Edge{
  8. int To;
  9. int Value;
  10. };
  11. struct Node{
  12. int Label;
  13. int Dis;
  14. bool operator < (const Node& b) const{
  15. return Dis > b.Dis;
  16. }
  17. };
  18. vector<Edge> Graph[10005];
  19. int n, m, k;
  20. long long Distant[10005][2];
  21. bool Visited[10005];
  22. void Dijkstra(bool X){
  23. memset(Visited, 0, sizeof(Visited));
  24. priority_queue<Node> Q;
  25. for (int i = 1; i <= n; ++i){
  26. Q.push((Node){i, Distant[i][X]});
  27. }
  28. for (int i = 1; i <= n; ++i){
  29. while (Q.size() && Visited[Q.top().Label]) Q.pop();
  30. if (Q.empty()) break;
  31. Node Now = Q.top();
  32. Q.pop();
  33. Visited[Now.Label] = true;
  34. for (vector<Edge>::iterator j = Graph[Now.Label].begin(); j != Graph[Now.Label].end(); ++j){
  35. if (!Visited[j -> To] && Distant[j -> To][X] > Distant[Now.Label][X] + j -> Value){
  36. Distant[j -> To][X] = Distant[Now.Label][X] + j -> Value;
  37. Q.push((Node){j -> To, Distant[j -> To][X]});
  38. }
  39. }
  40. }
  41. }
  42. int main(int argc, char const *argv[]){
  43. ios::sync_with_stdio(false);
  44. cin >> n >> m >> k;
  45. for (int i = 1; i <= m; ++i){
  46. int P1, P2, T;
  47. cin >> P1 >> P2 >> T;
  48. Graph[P1].push_back((Edge){P2, T});
  49. Graph[P2].push_back((Edge){P1, T});
  50. }
  51. int Now = 0, Last = 1;
  52. memset(Distant, 0x3f, sizeof(Distant));
  53. Distant[1][Now] = 0;
  54. Visited[1] = true;
  55. Dijkstra(Now);
  56. long long Ans = Distant[n][Now];
  57. while (k--){
  58. Now ^= 1;
  59. Last ^= 1;
  60. //通过 Now 和 Last 实现巧妙的保存上次的距离数组
  61. for (int i = 1; i <= n; ++i){
  62. Distant[i][Now] = Distant[i][Last];
  63. }
  64. //连边
  65. for (int i = 1; i <= n; ++i){
  66. for (vector<Edge>::iterator j = Graph[i].begin(); j != Graph[i].end(); ++j){
  67. Distant[j -> To][Now] = min(Distant[j -> To][Now], Distant[i][Last]);
  68. }
  69. }
  70. Dijkstra(Now);
  71. Ans = min(Ans, Distant[n][Now]);
  72. }
  73. cout << Ans;
  74. return 0;
  75. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注