1267. 路障(block.pas/c/cpp)
(File IO): input:block.in output:block.out
Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
Goto ProblemSet做法:其实次短路可以用spfa在更新最短路的同时更新一下次短路就好了,但我头铁打了A*
代码如下:
View Code
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <iostream> 5 #include <queue> 6 #include <algorithm> 7 #include <cstdlib> 8 #define N 400007 9 using namespace std; 10 int n, m, tot, ans; 11 struct edge 12 { 13 int to, next, w; 14 }e[N]; 15 int ls[N], f[N], list[N]; 16 int times[N]; 17 bool v[N]; 18 struct A_node 19 { 20 int g, h, p; 21 bool operator < (A_node x) const 22 { 23 return x.g + x.h < g + h; 24 } 25 }; 26 priority_queue<A_node>Q; 27 28 void add(int x, int y, int z) 29 { 30 e[++tot].to = y; 31 e[tot].next = ls[x]; 32 e[tot].w = z; 33 ls[x] = tot; 34 e[++tot].to = x; 35 e[tot].next = ls[y]; 36 e[tot].w = z; 37 ls[y] = tot; 38 } 39 40 void spfa() 41 { 42 for (int i = 1; i <= n; i++) 43 f[i] = 10000007; 44 f[n] = 0; 45 int h = 0, t = 0; 46 list[++t] = n; 47 v[n] = 1; 48 while (h < t) 49 { 50 int p = list[++h]; 51 for (int i = ls[p]; i; i = e[i].next) 52 if (f[p] + e[i].w < f[e[i].to]) 53 { 54 f[e[i].to] = f[p] + e[i].w; 55 if (!v[e[i].to]) 56 { 57 v[e[i].to] = 1; 58 list[++t] = e[i].to; 59 } 60 } 61 v[p] = 0; 62 } 63 } 64 65 int A_star() 66 { 67 A_node t1, tmp; 68 t1.p = 1, t1.g = 0, t1.h = 0; 69 Q.push(t1); 70 while (!Q.empty()) 71 { 72 t1 = Q.top(); Q.pop(); 73 times[t1.p]++; 74 if (times[t1.p] == 2 && t1.p == n) return t1.h + t1.g; 75 if (times[t1.p] > 2) continue; 76 for (int i = ls[t1.p]; i; i = e[i].next) 77 { 78 tmp.p = e[i].to; 79 tmp.g = f[e[i].to]; 80 tmp.h = e[i].w + t1.h; 81 Q.push(tmp); 82 } 83 } 84 85 } 86 87 int main() 88 { 89 freopen("block.in", "r", stdin); 90 freopen("block.out", "w", stdout); 91 scanf("%d%d", &n, &m); 92 int x, y, z; 93 for (int i = 1; i<= m; i++) 94 { 95 scanf("%d%d%d", &x, &y, &z); 96 add(x, y, z); 97 } 98 spfa(); 99 ans = A_star(); 100 printf("%d", ans); 101 }