简单最短路
#include<stdio.h> #include<string.h> #define N 1010 #define inf 0x3fffffff int n,m,vis[N],dis[N],cost[N]; int map[N][N],cot[N][N],s,t; void dijkstra() { int i,j,k,min; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { dis[i]=inf; cost[i]=inf; } dis[s]=0; cost[s]=0; for(i=1;i<=n;i++) { min=inf;k=-1; for(j=1;j<=n;j++) { if(min>dis[j]&&vis[j]==0) { k=j; min=dis[j]; } } if(k==-1)break; vis[k]=1; for(j=1;j<=n;j++) { 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,x,y,w,cont; while(scanf("%d%d",&n,&m),n||m) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { map[i][j]=inf; cot[i][j]=inf; } for(i=0;i<m;i++) { scanf("%d%d%d%d",&x,&y,&w,&cont); if(map[x][y]>w||(map[x][y]==w&&cot[x][y]>cont)) { map[x][y]=map[y][x]=w; cot[x][y]=cot[y][x]=cont; } } scanf("%d%d",&s,&t); dijkstra(); printf("%d %d\n",dis[t],cost[t]); } return 0; }