首页 > 代码库 > [POJ3463] Sightseeing（次短路 Heap + Dijkstra）
[POJ3463] Sightseeing（次短路 Heap + Dijkstra）
传送门
用dijkstra比较好，spfa可能有的重复
dis[x][2]:dis[x][0]表示起点到x的最短路、dis[x][1]表示起点到x的次短路；
tot[x][2]:tot[x][0]表示起点到x的最短路条数、tot[x][1]表示起点到x的次短路的条数；
vis[x][2]对应于x和0、1功能为记录该点是否被访问！
那么如何更新最小和次小路呢？显然我们容易想到下面的方法：
1.if(x<最小)更新最小，次小；
2.else if(x==最小)更新方法数；
3.else if(x<次小)更新次小；
4.else if(x==次小)更新方法数；
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 struct heap 10 { 11 int x, y, z; 12 heap(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {} 13 bool operator < (const heap &rhs) const 14 { 15 return y > rhs.y; 16 } 17 }; 18 19 const int MAXM = 10001, MAXN = 1001; 20 int T, n, m, cnt; 21 int dis[MAXN][2], head[MAXN], to[MAXM << 1], next[MAXM << 1], val[MAXM << 1], tot[MAXN][2]; 22 priority_queue <heap> q; 23 bool vis[MAXN][2]; 24 25 inline int read() 26 { 27 int x = 0, f = 1; 28 char ch = getchar(); 29 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 30 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 31 return x * f; 32 } 33 34 inline void add(int x, int y, int z) 35 { 36 to[cnt] = y; 37 val[cnt] = z; 38 next[cnt] = head[x]; 39 head[x] = cnt++; 40 } 41 42 inline void dijkstra(int s) 43 { 44 int i, u, v, d, p; 45 heap now; 46 memset(vis, 0, sizeof(vis)); 47 memset(tot, 0, sizeof(tot)); 48 memset(dis, 127 / 3, sizeof(dis)); 49 dis[s][0] = 0; 50 tot[s][0] = 1; 51 q.push(heap(s, 0, 0)); 52 while(!q.empty()) 53 { 54 now = q.top(); 55 q.pop(); 56 u = now.x; 57 p = now.z; 58 if(vis[u][p]) continue; 59 vis[u][p] = 1; 60 for(i = head[u]; i ^ -1; i = next[i]) 61 { 62 v = to[i]; 63 if(dis[v][0] > dis[u][p] + val[i]) 64 { 65 dis[v][1] = dis[v][0]; 66 tot[v][1] = tot[v][0]; 67 dis[v][0] = dis[u][p] + val[i]; 68 tot[v][0] = tot[u][p]; 69 q.push(heap(v, dis[v][0], 0)); 70 q.push(heap(v, dis[v][1], 1)); 71 } 72 else if(dis[v][0] == dis[u][p] + val[i]) tot[v][0] += tot[u][p]; 73 else if(dis[v][1] > dis[u][p] + val[i]) 74 { 75 dis[v][1] = dis[u][p] + val[i]; 76 tot[v][1] = tot[u][p]; 77 q.push(heap(v, dis[v][1], 1)); 78 } 79 else if(dis[v][1] == dis[u][p] + val[i]) tot[v][1] += tot[u][p]; 80 } 81 } 82 } 83 84 int main() 85 { 86 int i, j, x, y, z, s, t; 87 T = read(); 88 while(T--) 89 { 90 n = read(); 91 m = read(); 92 cnt = 0; 93 memset(head, -1, sizeof(head)); 94 for(i = 1; i <= m; i++) 95 { 96 x = read(); 97 y = read(); 98 z = read(); 99 add(x, y, z);100 }101 s = read();102 t = read();103 dijkstra(s);104 if(dis[t][1] == dis[t][0] + 1) tot[t][0] += tot[t][1];105 printf("%d\n", tot[t][0]);106 }107 }
[POJ3463] Sightseeing（次短路 Heap + Dijkstra）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。