3363=数据结构实验之图论七：驴友计划

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define INF 0x3f3f3f3f
 5 int map[1000][1000],map2[1000][1000];
 6 int n;
 7 void floyed()
 8 {
 9     int i,j,k;
10     for(k=0; k<n; k++)
11     {
12         for(i=0; i<n; i++)
13         {
14             for(j=0; j<n; j++)
15             {
16                 if(map[i][j]>map[i][k]+map[k][j])
17                 {
18                     map[i][j]=map[i][k]+map[k][j];
19                     map2[i][j]=map2[i][k]+map2[k][j];
20                 }
21                 else if(map[i][j]==map[i][k]+map[k][j])
22                 {
23                     if(map2[i][j]>map2[i][k]+map2[k][j])
24                         map2[i][j]=map2[i][k]+map2[k][j];
25 
26                 }
27             }
28         }
29     }
30 }
31 int main()
32 {
33     int T;
34     scanf("%d",&T);
35     while(T--)
36     {
37         int m,begin,end,a,b,c,d;
38         scanf("%d %d",&n,&m);
39         scanf("%d %d",&begin,&end);
40         memset(map,INF,sizeof(map));
41         memset(map2,0,sizeof(map2));
42         while(m--)
43         {
44             scanf("%d %d %d %d",&a,&b,&c,&d);
45             map[a][b]=map[b][a]=c;
46             map2[a][b]=map2[b][a]=d;
47         }
48         floyed(n);
49         printf("%d %d
",map[begin][end],map2[begin][end]);
50     }
51     return 0;
52 }