; if(dis2[s][u]!=inf&&dis2[s][v]>dis2[s][u]+g2[i].w) { dis2[s][v]=dis2[s][u]+g2[i].w; pre2[s][v]=u; if(!mark[v]) { q.push(v); mark[v]=1; } } } } } /*void path(int s,int t,int pre[N][N]) { if(s==t) return ; path(pre[t][s],t,pre); printf(" %d",s); }*/ int main() { int T,n,m,k,u,v,w,i,j; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); t1=t2=0; for(i=0;i
=inf||dis1[j][i]==-1) continue; double tmp=1.0*dis1[j][i]/dis2[i][j]; if(tmp>ans) { ans=tmp; s=i;t=j; } } } printf("%d ",s); i=s;j=t;k=0; int a[N]; //记录答案路径 while(pre2[i][j]!=s) //从终点向起始点找路径 { //到起始点结束 a[k++]=pre2[i][j]; j=pre2[i][j]; } for(i=k-1;i>=0;i--) printf("%d ",a[i]); printf("%d ",t); i=t;j=s;k=0; while(pre1[i][j]!=t) { a[k++]=pre1[i][j]; j=pre1[i][j]; } for(i=k-1;i>=0;i--) printf("%d ",a[i]); printf("%d\n",s); // path(t,s,pre2); // path(s,t,pre1); printf("%.3f\n",ans); } return 0; }
|