题意：
计算 1 和 n 两点间最短路的路径和的两倍
题解：
1 计算最短路
2 枚举没一条边到两端的距离加上本身长度，判断是等于最短路长度
3 若是的，那么这条边可以当做最短路的一条边
下面是堆优化最短路（源点到各个点的最短路）：
#include<queue> #include<vector> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f3f; const int maxn=10000+5; struct Edge { int from, to, dist; Edge(){} Edge(int u, int v, int d) :from(u), to(v), dist(d){} }; struct HeapNode { int d, u; HeapNode(int x, int y) :d(x), u(y){} bool operator < (const HeapNode& rhs) const{ return d > rhs.d; } }; struct Dijkstra { int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; int d[maxn]; int p[maxn]; void init(int n) { this->n = n; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdges(int from, int to, int dist) { edges.push_back(Edge(from,to,dist)); m = edges.size(); G[from].push_back((m - 1)); } void dijkstra(int s) { priority_queue<HeapNode> Q; for (int i = 0; i < n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push(HeapNode(0,s)); while (!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if (done[u]) continue; done[u] = true; for (int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = e.from; Q.push(HeapNode(d[e.to],e.to)); } } } } }t[2]; int n,m; Edge a[250005]; int main() { //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { t[0].init(n); t[1].init(n); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); t[0].AddEdges(u,v,w); t[0].AddEdges(v,u,w); t[1].AddEdges(u,v,w); t[1].AddEdges(v,u,w); a[i].from=u; a[i].to=v; a[i].dist=w; } t[0].dijkstra(0); t[1].dijkstra(n-1); ll value=t[0].d[n-1]; ll ans=0; for(int i=0;i<m;i++) { int u=a[i].from,v=a[i].to,w=a[i].dist; if((t[0].d[u]+t[1].d[v]+w==value)||(t[0].d[v]+t[1].d[u]+w==value)) ans+=w; } printf("%lld\n",ans*2); } return 0; }
