HDU 2544（简单最短路）

http://acm.hdu.edu.cn/showproblem.php?pid=2544

 1 /*
 2 使用pair代替结构
 3 */
 4 
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <queue>
 8 #include <vector>
 9 using namespace std;
10 const int Ni = 10000;
11 const int INF = 1<<27;
12 
13 typedef pair<int,int> pa;
14 
15 int dis[Ni],n;//dis使用1-n的部分
16 
17 vector<pair<int,int> > eg[Ni];
18 
19 void Dijkstra(int s)
20 {
21           int i,j;
22           for(i=0;i<=n;i++)//要到n
23                     dis[i] = INF;
24           priority_queue<pa> q;  //优先级队列：小顶堆
25           dis[s] = 0;
26           q.push(make_pair(s,dis[s]));
27 
28           while(!q.empty())
29           {
30                     pa x = q.top();
31                     q.pop();
32                     int w = x.first;
33                     for(j = 0;j<eg[w].size();j++)//遍历x的所有邻接点
34                     {
35                               pa y = eg[w][j];//y是x的邻接点
36                               int u = y.first;
37                               if(dis[u]>x.second+y.second)
38                               {
39                                         dis[u] = x.second+y.second;
40                                         q.push(make_pair(u,dis[u]));
41                               }
42                     }
43           }
44 
45 }
46 
47 
48 int main()
49 {
50           int m,a,b,d;//关系个数
51           while(cin>>n>>m,m+n)
52           {
53                     for(int i = 0;i<=n;i++)
54                               eg[i].clear();//初始化
55                     while(m--)
56                     {
57                               cin>>a>>b>>d;
58                               eg[a].push_back(make_pair(b,d));
59                               eg[b].push_back(make_pair(a,d));
60                     }
61 
62                     Dijkstra(1);
63                     if(dis[n]!=INF)
64                               cout<<dis[n]<<endl;
65                     else
66                               cout<<"-1
";
67           }
68 
69           return 0;
70 }

同换C，从62到了15MS

要注意下标

 1 #include <cstdio>
 2 using namespace std;
 3 const int L = 1010;
 4 const int INF = 1<<27;
 5 
 6 int map[L][L];
 7 int vis[L];
 8 int dis[L];
 9 
10 int n,m;
11 
12 void Dijkstra(int s)
13 {
14           int i,j,k;
15           int min;
16           for(i = 0;i<=n;i++)
17           {
18                     dis[i] = map[s][i];
19                     vis[i] = 0;
20           }
21 
22           vis[s] = 1;
23           dis[s] = 0;
24 
25           for(i = 0;i<=n;i++)
26           {
27                     min = INF;
28                     for(j = 0;j<=n;j++)
29                     {
30                               if(dis[j]<min && !vis[j])
31                               {
32                                         k = j;
33                                         min = dis[j];
34                               }
35                     }
36 
37                     vis[k] = 1;
38 
39                     for(j = 0;j<=n;j++)
40                     {
41                               if(dis[j] > min+map[k][j] && !vis[j])
42                               {
43                                         dis[j] = min+map[k][j];
44                               }
45                     }
46           }
47 }
48 
49 void init()
50 {
51           int i,j;
52           for(i = 0;i<=n;i++)
53           {
54                     map[i][i] = 0;
55                     for(j = i+1;j<=n;j++)
56                     {
57                               map[i][j] = map[j][i] = INF;
58                     }
59           }
60 
61           while(m--)
62           {
63                     int a,b,w;
64                     scanf("%d%d%d",&a,&b,&w);
65                     if(w<map[a][b])//可能有同两点，但不同weight
66                     {
67                               map[a][b] = w;
68                               map[b][a] = w;
69                     }
70           }
71 }
72 
73 
74 int main()
75 {
76           while(scanf("%d%d",&n,&m),n+m)
77           {
78                     int r,t;
79 
80                     init();
81 
82 
83                     Dijkstra(1);
84 
85                     if(dis[n]!=INF)
86                               printf("%d
",dis[n]);
87                     else
88                               printf("-1
");
89 
90           }
91 
92           return 0;
93 }