[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.elseif(x==最小)更新方法数；
3.elseif(x<次小)更新次小；
4.elseif(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 13 bool operator < (const heap &rhs) const 14 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 33 34 inline void add(int x, int y, int z) 35 41 42 inline void dijkstra(int s) 43 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 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 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 }
View Code

上一篇：矩阵运算所满足的定律

下一篇：[BZOJ2462] [BeiJing2011]矩阵模板（二维Hash）

---

stl 最短路 堆 dijkstra