1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
| #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #define MAX 1000010 #define LEN 1010 using namespace std; int distD[LEN]; int distP[LEN]; int mapD[LEN][LEN]; int mapP[LEN][LEN]; bool visited[LEN];
void init() { int i,j; for(i=0; i<LEN; i++) { for(j=0; j<LEN; j++) { mapD[i][j]=MAX; mapP[i][j]=MAX; } } }
void dijstra(int n,int start) { int i,j,min,k; for(i=1; i<=n; i++) { visited[i]=false; distD[i]=mapD[start][i]; distP[i]=mapP[start][i]; } visited[start]=true; distD[start]=0; for(i=1; i<=n; i++) { min=MAX; for(j=1; j<=n; j++) { if(!visited[j] && distD[j]<min) { min=distD[j]; k=j; } } if(min==MAX) break; visited[k]=true; for(j=1; j<=n; j++) { if(!visited[j]) { if(distD[j]>distD[k]+mapD[k][j]) { distD[j]=distD[k]+mapD[k][j]; distP[j]=distP[k]+mapP[k][j]; } else if(distD[j]==distD[k]+mapD[k][j]) { if(distP[j]>distP[k]+mapP[k][j]) { distP[j]=distP[k]+mapP[k][j]; } } } } } } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; init(); int i,j,a,b,d,p,s,t; for(i=0; i<m; i++) { scanf("%d%d%d%d",&a,&b,&d,&p); if(mapD[a][b]>d) { mapD[a][b]=mapD[b][a]=d; mapP[a][b]=mapP[b][a]=p; } } scanf("%d%d",&s,&t); dijstra(n,s); printf("%d %d\n",distD[t],distP[t]); } return 0; }
|