POJ2387（dijkstra堆优化）

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #include<queue>
 8 #define maxn 1005
 9 #define ms(x,n) memset(x,n,sizeof x);
10 const int inf=0x3f3f3f3f;
11 using namespace std;
12 int n,t;
13 int u,v,w;
14 int cost[1005][1005];
15 int d[1005];
16 bool vis[1005];
17 void dij(int s)
18 {
19     int i,j;
20     ms(vis,0);
21     memset(d,0x3f,sizeof d);
22     d[s]=0;
23     for(i=1;i<=n;i++)
24     {
25         int p=inf,e=-1;
26         for(j=1;j<=n;j++)
27         {
28             if(!vis[j]&&d[j]<p)
29             {
30                 p=d[j];
31                 e=j;
32             }
33         }
34         if(e==-1)return;
35         vis[e]=1;
36         for(j=1;j<=n;j++)
37         {
38             if(!vis[j]&&d[j]>cost[e][j]+d[e])
39                 {d[j]=cost[e][j]+d[e];
40                 }
41         }
42     }
43 }
44 int main()
45 {
46     int i,j;
47     cin>>t>>n;
48     for(i=1;i<=n;i++)
49      for(j=1;j<=n;j++)
50         if(i!=j)
51         cost[i][j]=inf;
52      else if(i==j)
53         cost[i][j]=0;
54     for(i=0;i<t;i++)
55     {
56         cin>>u>>v>>w;
57         cost[u][v]=cost[v][u]=min(cost[u][v],w);
58     }
59      dij(1);
60      cout<<d[n];
61 }

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #include<queue>
 8 #define maxn 1005
 9 #define ms(x,n) memset(x,n,sizeof x);
10 const int inf=0x3f3f3f3f;
11 using namespace std;
12 int n,t;
13 int u,v,w;
14 int cost[1005][1005];
15 int d[1005];
16 bool vis[1005];
17 typedef pair<int,int> p;//cost[],点的编号
18 vector<p>g[maxn];
19 void dij(int s)
20 {
21     ms(vis,0);
22     ms(d,0x3f);
23     d[s]=0;
24     priority_queue<p,vector<p>,greater<p> >q;
25     q.push(p(d[s],s));
26     while(!q.empty())
27     {
28         p cur=q.top();
29         q.pop();
30         u=cur.second;
31         //if(cur.first<d[u])continue;
32         int sz=g[u].size();
33         for(int i=0;i<sz;i++)
34         {
35             v=g[u][i].second;
36             w=g[u][i].first;
37             if(d[v]>d[u]+w)
38             {d[v]=d[u]+w;
39             q.push(p(d[v],v));
40             }
41         }
42     }
43 }
44 int main()
45 {
46     int i;
47     cin>>t>>n;
48     for(i=0;i<n;i++)
49         g[i].clear();
50     for(i=0;i<t;i++)
51     {
52         cin>>u>>v>>w;
53         u--,v--;
54         g[u].push_back(p(w,v));
55         g[v].push_back(p(w,u));
56     }
57     dij(0);
58     cout<<d[n-1];
59 }