不说什么了，模板题
题目数据有点弱，不严格的次短路也能ac。。。。
View Code
1 #include <cstring> 2 #include <cstdlib> 3 #include <algorithm> 4 #include <iostream> 5 #include <cstdio> 6 7 #define N 100000 8 #define M 2000000 9 10 using namespace std; 11 12 struct HP 13 { 14 int x,d; 15 }hp[M]; 16 17 int head[N],next[M],dis[N],to[M],len[M],cnt,n,qk,m,q[M],cs[N],size; 18 bool vis[N]; 19 20 inline void add(int u,int v,int w) 21 { 22 to[cnt]=v; len[cnt]=w; next[cnt]=head[u]; head[u]=cnt++; 23 } 24 25 inline bool cmp(const HP &a,const HP &b) 26 { 27 return a.d+dis[a.x]>b.d+dis[b.x]; 28 } 29 30 void read() 31 { 32 memset(head,-1,sizeof head); cnt=0; 33 for(int i=1,a,b,c;i<=m;i++) 34 { 35 scanf("%d%d%d",&a,&b,&c); 36 add(a,b,c); add(b,a,c); 37 } 38 qk=2; 39 } 40 41 void spfa() 42 { 43 memset(dis,0x3f,sizeof dis); 44 int h=1,t=2,sta; 45 q[1]=n; vis[n]=true; dis[n]=0; 46 while(h<t) 47 { 48 sta=q[h++]; 49 vis[sta]=false; 50 for(int i=head[sta];~i;i=next[i]) 51 if(dis[to[i]]>dis[sta]+len[i]) 52 { 53 dis[to[i]]=dis[sta]+len[i]; 54 if(!vis[to[i]]) vis[to[i]]=true,q[t++]=to[i]; 55 } 56 } 57 } 58 59 int bfs() 60 { 61 memset(cs,0,sizeof cs); 62 bool fg=false;int mindis=-1; 63 hp[1].x=1; hp[1].d=0; size=1; 64 while(size) 65 { 66 HP sta=hp[1]; 67 pop_heap(hp+1,hp+1+size,cmp); size--; 68 69 if(sta.x!=n) cs[sta.x]++; 70 else if(sta.d!=mindis) cs[sta.x]++; 71 72 if(sta.x==n&&!fg) 73 { 74 mindis=sta.d; 75 fg=true; 76 } 77 if(cs[n]==qk) return sta.d; 78 if(cs[sta.x]>qk) continue; 79 for(int i=head[sta.x];~i;i=next[i]) 80 { 81 size++; 82 hp[size].x=to[i]; hp[size].d=sta.d+len[i]; 83 push_heap(hp+1,hp+1+size,cmp); 84 } 85 } 86 } 87 88 void go() 89 { 90 spfa(); 91 if(1==n) qk++; 92 printf("%d\n",bfs()); 93 } 94 95 int main() 96 { 97 while(scanf("%d%d",&n,&m)!=EOF) 98 { 99 read(); 100 go(); 101 } 102 return 0; 103 }