题目:
Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.
The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.
The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).
Input
Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)
Output
Sample Input
4 4 1 2 100 2 4 200 2 3 250 3 4 100
Sample Output
450
Hint
1 #include <map> 2 #include <set> 3 #include <list> 4 #include <stack> 5 #include <queue> 6 #include <deque> 7 #include <cmath> 8 #include <ctime> 9 #include <string> 10 #include <limits> 11 #include <cstdio> 12 #include <vector> 13 #include <iomanip> 14 #include <cstdlib> 15 #include <cstring> 16 #include <istream> 17 #include <iostream> 18 #include <algorithm> 19 #define ci cin 20 #define co cout 21 #define el endl 22 #define Scc(c) scanf("%c",&c) 23 #define Scs(s) scanf("%s",s) 24 #define Sci(x) scanf("%d",&x) 25 #define Sci2(x, y) scanf("%d%d",&x,&y) 26 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z) 27 #define Scl(x) scanf("%I64d",&x) 28 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y) 29 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z) 30 #define Pri(x) printf("%d ",x) 31 #define Prl(x) printf("%I64d ",x) 32 #define Prc(c) printf("%c ",c) 33 #define Prs(s) printf("%s ",s) 34 #define For(i,x,y) for(int i=x;i<y;i++) 35 #define For_(i,x,y) for(int i=x;i<=y;i++) 36 #define FFor(i,x,y) for(int i=x;i>y;i--) 37 #define FFor_(i,x,y) for(int i=x;i>=y;i--) 38 #define Mem(f, x) memset(f,x,sizeof(f)) 39 #define LL long long 40 #define ULL unsigned long long 41 #define MAXSIZE 100005 42 #define INF 0x3f3f3f3f 43 44 const int mod=1e9+7; 45 const double PI = acos(-1.0); 46 47 48 using namespace std; 49 50 typedef pair<int,int>pii; 51 struct edge 52 { 53 int to,w; 54 edge(int x,int y) 55 { 56 to=x; 57 w=y; 58 } 59 }; 60 vector<edge>G[MAXSIZE];//邻接表储存 61 int dis[MAXSIZE];//最短 62 int dis2[MAXSIZE];//次短 63 64 int n,r; 65 void solve() 66 { 67 priority_queue<pii,vector<pii>,greater<pii> >q;//注意这个队列first存的是到每点的最短距离,second存的这个点 68 Mem(dis,INF); 69 Mem(dis2,INF); 70 q.push(pii(0,1)); 71 dis[1]=0; 72 while(!q.empty()) 73 { 74 pii p=q.top(); 75 q.pop(); 76 int v=p.second,d=p.first; 77 if(dis2[v]<d) 78 continue;//到v的距离比次短路短(肯定也比最短路短),终止本次循环 79 for(int i=0; i<G[v].size(); i++) 80 { 81 edge &e=G[v][i]; 82 int d2=e.w+d; 83 if(dis[e.to]>dis[v]+e.w)//更新最短路径if(dis[e.to]>d2) 84 { 85 swap(dis[e.to],d2); 86 q.push(pii(dis[e.to],e.to)); 87 } 88 if(dis2[e.to]>d2&&dis[e.to]<d2)//注意这个两个条件,后面那个条件可以不要 89 { 90 swap(dis2[e.to],d2); 91 q.push(pii(dis2[e.to],e.to)); 92 } 93 } 94 } 95 Pri(dis2[n]); 96 } 97 int main() 98 { 99 Sci2(n,r); 100 For_(i,1,r) 101 { 102 int u,v,w; 103 Sci3(u,v,w); 104 G[u].push_back(edge(v,w)); 105 G[v].push_back(edge(u,w)); 106 } 107 solve(); 108 return 0; 109 }