C語言源碼： [cpp] #include<stdio.h> #include<limits.h> #define maxsize 1010 int E[maxsize][maxsize][2];//0放長度，1放花費 int T[maxsize]; int L[maxsize][2]; int main() { int n,m,a,b,d,p,i,j,s,t,k,min,fmin; scanf("%d %d",&n,&m);//n是頂點數，m是邊數 while(n||m) { for(i=0;i<n;i++) { for(j=0;j<n;j++) { E[i][j][0]=INT_MAX; E[i][j][1]=INT_MAX; } } for(i=0;i<m;i++) { scanf("%d %d %d %d",&a,&b,&d,&p); E[a-1][b-1][0]=d; E[a-1][b-1][1]=p; E[b-1][a-1][0]=d; E[b-1][a-1][1]=p; } scanf("%d %d",&s,&t); s--; t--; for(i=0;i<n;i++) { T[i]=0; L[i][0]=INT_MAX; L[i][1]=INT_MAX; } L[s][0]=0; L[s][1]=0; T[s]=1; k=s; while(k!=t) { for(i=0;i<n;i++) { if(T[i]==0&&E[k][i][0]!=INT_MAX) { if(L[k][0]+E[k][i][0]<L[i][0]) { L[i][0]=L[k][0]+E[k][i][0]; L[i][1]=L[k][1]+E[k][i][1]; } else if((L[k][0]+E[k][i][0]==L[i][0])&&(L[k][1]+E[k][i][1]<L[i][1])) L[i][1]=L[k][1]+E[k][i][1]; } } fmin=-1; min=INT_MAX; for(i=0;i<n;i++) { if(T[i]==0&&L[i][0]<min) { min=L[i][0]; fmin=i; } } T[fmin]=1; k=fmin; } printf("%d %d\n",L[t][0],L[t][1]); scanf("%d %d",&n,&m); } }
