C語言源碼： [cpp] #include<stdio.h> #include<limits.h> typedef struct node { int length,cost; }node; node A[600][600]; int visited[600]; node T[600]; int Stack[600][600]; int top[600]; int main() { int n,m,i,j,s,t,a,b,length,cost,minlength,mincost,fmin,k; scanf("%d %d %d %d",&n,&m,&s,&t); for(i=0;i<n;i++) { for(j=0;j<n;j++) A[i][j].length=INT_MAX; visited[i]=0; T[i].length=INT_MAX; T[i].cost=INT_MAX; top[i]=0; } for(i=0;i<m;i++) { scanf("%d %d %d %d",&a,&b,&length,&cost); if(length<A[a][b].length||(length==A[a][b].length&&cost<A[a][b].cost)) { A[a][b].length=length; A[a][b].cost=cost; } A[b][a].length=A[a][b].length; A[b][a].cost=A[a][b].cost; } visited[s]=1; T[s].length=0; T[s].cost=0; i=s; top[s]=1; Stack[s][0]=s; while(i!=t) { for(j=0;j<n;j++) { if(visited[j]==0) { if(A[i][j].length!=INT_MAX) { if(T[i].length+A[i][j].length<T[j].length||(T[i].length+A[i][j].length==T[j].length&&T[i].cost+A[i][j].cost<T[j].cost)) { T[j].length=T[i].length+A[i][j].length; T[j].cost=T[i].cost+A[i][j].cost; top[j]=top[i]; for(k=0;k<top[i];k++) Stack[j][k]=Stack[i][k]; } } } } minlength=INT_MAX; mincost=INT_MAX; for(j=0;j<n;j++) { if(visited[j]==0&&(T[j].length<minlength||(T[j].length==minlength&&T[j].cost<mincost))) { fmin=j; minlength=T[j].length; mincost=T[j].cost; } } visited[fmin]=1; Stack[fmin][top[fmin]++]=fmin; i=fmin; } for(i=0;i<top[t];i++) printf("%d ",Stack[t][i]); printf("%d %d\n",T[t].length,T[t].cost); return 0; }
