poj 2387 Til the Cows Come Home(dijkstra算法)

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int map[2010][2010],Min,node[2010],vis[2010],t,q;
 5 const int INF=9999999;
 6 
 7 void set()
 8 {
 9     for (int i=1; i<=2001; i++)
10     {
11         node[i]=INF;
12         vis[i]=0;
13         for (int j=1; j<=2001; j++)
14             map[i][j]=INF;
15     }
16 }
17 
18 int dijkstra(int m)
19 {
20     int tm=m;
21     vis[m]=1;
22     node[m]=0;
23     for (int k=2; k<=q; k++)
24     {
25         Min=INF;
26         for (int i=1; i<=q; i++)
27             if (!vis[i])
28             {
29                 if (node[i]>map[tm][i]+node[tm])
30                 {
31                     node[i]=map[tm][i]+node[tm];
32                     //cout<<map[tm][i]<<" "<<node[i]<<endl;
33                 }
34                 if (Min>node[i])
35                 {
36                     //cout<<Min<<endl;
37                     Min=node[i];
38                     m=i;
39                 }
40             }
41         vis[m]=1;
42         tm=m;
43     }
44     return Min;
45 }
46 
47 int main ()
48 {
49     int n;
50     //memset(map,0,sizeof(map));
51     while (~scanf("%d%d",&t,&n))
52     {
53         q=0;
54         set();
55         while (t--)
56         {
57             int a,b,c;
58             scanf("%d%d%d",&a,&b,&c);
59             if (q<a)
60                 q=a;
61             else if (q<b)
62                 q=b;
63             if (map[a][b]>c)
64             {
65                 map[a][b]=map[b][a]=c;
66             }
67         }
68         dijkstra(n);
69         printf("%d\n",node[1]);
70     }
71     return 0;
72 }