九度 OJ1008 hdu 3790

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct node
 4 {
 5     int d;
 6     int p;
 7     
 8 }g[1001][1001];
 9 #define inf 0x3f3f3f3f
10 int lowcost[1001],price[1001],used[1001];
11 int s,t;
12 void dijstra(int n,int a)
13 {
14     int i,j,k,min;
15     memset(used,0,sizeof(used));
16     for(i=1;i<=n;i++)
17     {
18         lowcost[i]=g[i][a].d;
19         price[i]=g[i][a].p;
20     }
21     used[a]=1;
22     for(i=1;i<=n;i++)
23     {
24         min=inf;
25         j=a;
26         for(k=1;k<=n;k++)
27         {
28             if(lowcost[k]<min&&!used[k])
29             {
30                 min=lowcost[k];
31                 j=k;
32             }
33         }
34         used[j]=1;
35         for(k=1;k<=n;k++)
36         {
37                 if(lowcost[j]+g[k][j].d<lowcost[k]&&!used[k])
38                 {
39                     lowcost[k]=lowcost[j]+g[k][j].d;
40                     price[k]=price[j]+g[k][j].p;                    
41                 }
42                 else if(lowcost[j]+g[k][j].d==lowcost[k]&&!used[k])
43                 {
44                     if(price[j]+g[k][j].p<price[k])
45                     price[k]=price[j]+g[k][j].p;
46                 }
47                 
48         }
49     }
50     printf("%d %d
",lowcost[t],price[t]);
51 }
52 
53 
54 int main()
55 {
56     int n,m,i,j,a,b,d,p;
57     while(scanf("%d %d",&n,&m)!=EOF&&n!=0||m!=0)
58     {
59     for(i=1;i<=n;i++)
60     {
61         for(j=1;j<=n;j++)
62         {
63         g[i][j].d=inf;
64         g[i][j].p=inf;
65        }
66         g[i][i].p=g[i][i].d=0;
67     }
68     for(i=0;i<m;i++)
69     {
70         scanf("%d %d %d %d",&a,&b,&d,&p);
71         if(g[a][b].d>d)
72         {
73         g[a][b].d=d;
74         g[a][b].p=p;
75         g[b][a].d=d;
76         g[b][a].p=p;
77         }
78         else if(g[a][b].d==d&&g[a][b].p>p)
79         {
80             g[a][b].p=p;
81             g[b][a].p=p;            
82         }
83     }
84     scanf("%d %d",&s,&t);
85     dijstra(n,s);
86    }
87     return 0;
88 }
View Code
记得考虑重便哦，和初始化尽量大，否则会WA；
浙大计算机研究生复试上机考试-2010年
更新于：2014-04-25 00:22:35