九度 OJ1008 Unsoved problem

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define inf 0xfffff
 4 int g[1001][1001];
 5 int lowcost[1000001],used[1000001];
 6 void dijstra(int n,int s)
 7 {
 8     int i,j,k,min;
 9     memset(lowcost,0,sizeof(lowcost));
10     memset(used,0,sizeof(used));
11     for(i=1;i<=n;i++)
12     lowcost[i]=g[i][s];
13     used[s]=1;
14     for(i=1;i<n;i++)
15     {
16         j=s;
17         min=inf;
18         for(k=1;k<=n;k++)
19         {
20             if(lowcost[k]<min&&!used[k])
21             min=lowcost[k],j=k;
22         }
23         used[k]=1;
24         for(k=1;k<=n;k++)
25         {
26             if(lowcost[j]+g[k][j]<lowcost[j]&&!used[k])
27             lowcost[k]=g[k][j]+lowcost[j],
28             g[k][s]=g[s][k]=lowcost[k];
29         }
30     
31 }
32 }
33 int main()
34 {
35     int n,m,a,b,d,p,i,j;
36     scanf("%d %d",&n,&m);
37     for(i=1;i<=n;i++)
38     {
39         for(j=1;j<=n;j++)
40         {
41             g[i][j]=inf;
42         }
43         g[i][i]=0;
44     }
45     for(i=0;i<m;i++)
46     {
47         scanf("%d %d %d %d",&a,&b,&d,&p);
48         g[a][b]=g[b][a]=d;
49     }
50     int s,t;
51     dijstra(n,s);
52     return 0;
53 }