相当于两个放在一起求了。。。
#include"stdio.h" #include"string.h" #define N 1002 #define inf 100000000000 int n,m; int dis[N]; int cost[N]; int mark[N]; int map[N][N]; int cot[N][N]; void dij(int s) { int i,j,k,min; for(i=1;i<=n;i++) { dis[i]=map[s][i]; cost[i]=cot[s][i]; } dis[s]=0; cost[s]=0; memset(mark,0,sizeof(mark)); for(i=1;i<=n;i++) { min=inf; for(j=1;j<=n;j++) { if(!mark[j]&&min>dis[j]) { min=dis[j]; k=j; } } if(min==inf)break; mark[k]=1; for(j=1;j<=n;j++) { if(mark[j]==1)continue; if(dis[j]>dis[k]+map[k][j]||(dis[j]==dis[k]+map[k][j]&&cost[j]>cost[k]+cot[k][j])) { dis[j]=dis[k]+map[k][j]; cost[j]=cost[k]+cot[k][j]; } } } } int main() { int i,j; while(scanf("%d%d",&n,&m),n||m) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map[i][j]=cot[i][j]=inf; } } int a,b,c,d; for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); if(map[a][b]>c||(map[a][b]==c&&cot[a][b]>d)) { map[a][b]=map[b][a]=c; cot[a][b]=cot[b][a]=d; } } scanf("%d%d",&a,&b); dij(a); printf("%d %d\n",dis[b],cost[b]); } return 0; }