SGU 185 Two shortest
4227 ワード
2本の最短ルートを探し出し、出力する.
FLOYEDでポイント間の最短ルートを求め,終点と原点の最短ルート上のポイントをネットワークストリーム中のポイントとして構築し,彼らのエッジもネットワークストリーム中のエッジである.
なんだかRE MLE WAがいっぱいで行コードが血だらけ..
FLOYEDでポイント間の最短ルートを求め,終点と原点の最短ルート上のポイントをネットワークストリーム中のポイントとして構築し,彼らのエッジもネットワークストリーム中のエッジである.
なんだかRE MLE WAがいっぱいで行コードが血だらけ..
#include<stdio.h> #include<string.h> #define LMT 410 #define eps 0xfffffff typedef struct { int u,v,c,next; }line; line e[170000];// 17000,RE short map[LMT][LMT];// int MLE int dis[LMT]; int next[LMT],fnext[LMT],lev[LMT],q[LMT],l[LMT],vis[LMT],all,n,m; void insert(int u,int v,int c) { e[all].u=u; e[all].v=v; e[all].c=c; e[all].next=next[u]; next[u]=all++; e[all].v=u; e[all].u=v; e[all].c=0; e[all].next=next[v]; next[v]=all++;//all 。。。 } int spfa(short s,short t) { short i,j, head,tail;head=tail=0; memset(vis,0,sizeof(vis)); for(i=0;i<n;i++)dis[i]=eps; dis[s]=0;vis[s]=1;q[tail++]=s; while(head!=tail) { i=q[head]; head=(head+1)%LMT; vis[i]=0; for(j=0;j<n;j++) if(map[i][j]!=-1&&dis[j]>dis[i]+map[i][j]) { dis[j]=dis[i]+map[i][j]; if(0==vis[j]) { vis[j]=1; q[tail]=j; tail=(tail+1)%LMT;// ,WA 。。 } } } return dis[t]<eps; } void output(short u) { printf("%d ",u+1); if(u==n-1)return; int x; for(x=next[u];x!=-1;x=e[x].next) if(0==e[x].c&&x%2==0) { e[x].c=-1; output(e[x].v); return; } } int bfs(int s,int t) { int head,tail,x,u,v; memset(lev,0,sizeof(lev)); head=tail=0;q[tail++]=s;lev[s]=1; while(head<tail) { u=q[head++]; for(x=next[u];x!=-1;x=e[x].next) { v=e[x].v; if(0==lev[v]&&e[x].c>0) { lev[v]=1+lev[u]; q[tail++]=v; } } } return lev[t]!=0; } int dfs(int s,int t) { int u,j,top,x,back,ret,min;top=0;q[top++]=s; ret=0;memcpy(fnext,next,sizeof(next));// fhead, ,WA , while(top>0) { u=q[top-1]; if(u==t) { min=eps; for(j=1;j<top;j++) { x=l[q[j]]; if(min>e[x].c) { min=e[x].c; back=j; } } for(j=1;j<top;j++) { x=l[q[j]]; e[x].c-=min; e[x^1].c+=min; } ret+=min; top=back; } else { for(x=fnext[u];x!=-1;x=fnext[u]=e[x].next) { if(e[x].c>0&&lev[e[x].v]==lev[u]+1) { q[top++]=e[x].v; l[e[x].v]=x; break; } } if(x==-1) { top--; lev[u]=0; } } } return ret; } int flow(int s,int t) { int ret=0; while(bfs(s,t)) ret+=dfs(s,t); return ret; } int main() { int i,j,w,s,t,f; while(scanf("%d%d",&n,&m)!=EOF) { memset(map,-1,sizeof(map)); for(i=0;i<n;i++) map[i][i]=0; while(m--) { scanf("%d%d%d",&i,&j,&w); i--;j--;map[j][i]=map[i][j]=w; } all=0;s=0;t=n-1; if(0==spfa(0,n-1)) { printf("No solution
"); continue; } all=0;memset(next,-1,sizeof(next)); for(i=0;i<n;i++) for(j=0;j<n;j++) if(map[i][j]!=-1&&dis[j]==dis[i]+map[i][j]) insert(i,j,1); f=flow(s,t); if(f>=2) { output(0);printf("
"); output(0);printf("
"); } else printf("No solution
"); } return 0; }