10806 - Dijkstra, Dijkstra.-------好题（想不到的思路！！）--两次spfa--神奇般的对了
#include<cstdlib>#include<iostream>#include<sstream>#include<cstdio>#include<cmath>#include<cstring>#include <algorithm>#include<vector>#include<set>#include<queue>#define LL long long#define inf 0x7f7f7f7f#define E 1e-9#define N 105#define M 2000000using namespace std;int n,m;int q[N];//循环队列int d[N];int inq[N],fa[N];int ma[N][N];void init(){ memset(inq,0,sizeof(inq)); fill(d+1,d+n+1,inf); d[1]=0;}void spfa(){ init(); int r=0,f=0; q[r++]=1; inq[1]=1; fa[1]=1; while(f!=r) { int u=q[f++]; if(f==N-1) f=0; for(int i=1; i<=n; i++) if(ma[u][i]!=inf) { if(d[i]>d[u]+ma[u][i]) { d[i]=d[u]+ma[u][i]; fa[i]=u; if(!inq[i]) { q[r++]=i; if(r==N-1) r=0; inq[i]=1; } } } inq[u]=0; }}int main(){#ifndef ONLINE_JUDGE freopen("ex.in","r",stdin);#endif while(scanf("%d",&n),n) { int x,y,z; scanf("%d",&m); memset(ma,0x7f,sizeof(ma)); for(int i=0; i<m; ++i) { scanf("%d%d%d",&x,&y,&z); ma[x][y]=ma[y][x]=z; }// cout<<"top="<<top<<endl;// for(int i=1; i<=n; i++)// {// cout<<"head[i]="<<head[i]<<endl;// for(int j=head[i]; j!=-1; j=next[j])// {// Node *p=&temp[j];// cout<<i<<" ";// }// cout<<endl;// } spfa(); int sum=d[n]; if(sum==inf) { printf("Back to jail\n"); continue; }// for(int i=1; i<=n; i++)// cout<<d[i]<<" ";// cout<<endl;// for(int i=1; i<=n; i++)// cout<<fa[i]<<" ";// cout<<endl; for(int i=n; i!=1; i=fa[i]) { ma[fa[i]][i]=inf; ma[i][fa[i]]=-ma[i][fa[i]]; } spfa();// for(int i=1; i<=n; i++)// cout<<d[i]<<" ";// cout<<endl;// for(int i=1; i<=n; i++)// cout<<fa[i]<<" ";// cout<<endl; if(d[n]==inf) { printf("Back to jail\n"); continue; } sum+=d[n]; printf("%d\n",sum); } return 0;}