axn]; void dijkstra_S() { memset(dist_S,63,sizeof(dist_S)); memset(vis,false,sizeof(vis)); memset(pre_S,-1,sizeof(pre_S)); dist_S[S]=0; for(int i=1;i<=n;i++) { int mark=-1,mindist=INF; for(int j=1;j<=n;j++) { if(!vis[j]&&dist_S[j]
dist_S[mark]+edge[j].cost) { dist_S[u]=dist_S[mark]+edge[j].cost; pre_S[u]=mark; } } } } } void dijkstra_E() { memset(dist_E,63,sizeof(dist_E)); memset(vis,false,sizeof(vis)); memset(pre_E,-1,sizeof(pre_E)); dist_E[E]=0; for(int i=1;i<=n;i++) { int mark=-1,mindist=INF; for(int j=1;j<=n;j++) { if(!vis[j]&&dist_E[j]
dist_E[mark]+edge[j].cost) { dist_E[u]=dist_E[mark]+edge[j].cost; pre_E[u]=mark; } } } } } vector
road; void next_S(int x) { road.push_back(x); if(pre_S[x]!=-1) next_S(pre_S[x]); } void next_E(int x) { road.push_back(x); if(pre_E[x]!=-1) next_E(pre_E[x]); } int main() { int cas=0; while(scanf("%d%d%d",&n,&S,&E)!=EOF) { init(); scanf("%d",&M); for(int i=0;i
temp) { ST=u; ED=v; ans=temp; CE=i; } temp=dist_S[v]+c+dist_E[u]; if(ans>temp) { ST=v; ED=u; ans=temp; CE=i; } } road.clear(); if(ST==-1) { next_S(E); int sz=road.size(); for(int i=sz-1;i>=0;i--) { if(i!=sz-1) putchar(32); printf("%d",road[i]); } } else { next_S(ST); int sz=road.size(); for(int i=sz-1;i>=0;i--) { if(i!=sz-1) putchar(32); printf("%d",road[i]); } road.clear(); next_E(ED); sz=road.size(); for(int i=0;i
|