hdu1874 畅通工程续 spfa/迪杰斯特拉

题目链接:

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

题意:

题解:

卿学姐视频： http://www.bilibili.com/video/av4224493/

代码:

spfa：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 205+10;
17 
18 std::vector<pair<int,int> > E[maxn];
19 
20 int n,m;
21 int d[maxn],inq[maxn];
22 
23 void init(){
24     for(int i=0; i<maxn; i++) E[i].clear();
25     for(int i=0; i<maxn; i++) inq[i] = 0;
26     for(int i=0; i<maxn; i++) d[i] = 1e9;
27 }
28 
29 int main(){
30     while(cin >> n >> m){
31         init();
32         for(int i=0; i<m; i++){
33             int u,v,w; scanf("%d%d%d",&u,&v,&w);
34             E[u].push_back(MP(v,w));
35             E[v].push_back(MP(u,w));
36         }
37 
38         int s,t;
39         scanf("%d%d",&s,&t);
40 
41         queue<int> Q;
42         Q.push(s), d[s]=0, inq[s]=0;
43         while(!Q.empty()){
44             int now = Q.front();
45             Q.pop(); inq[now] = 0;
46             for(int i=0; i<(int)E[now].size(); i++){
47                 int v = E[now][i].first, w = E[now][i].second;
48                 if(d[now]+w < d[v]){
49                     d[v] = d[now]+w;
50                     if(inq[v]==1) continue;
51                     inq[v] = 1;
52                     Q.push(v);
53                 }
54             }
55         }
56 
57         if(d[t] == 1e9) printf("-1
");
58         else printf("%d
",d[t]);
59     }
60 
61     return 0;
62 }

dij：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 205+10;
17 
18 std::vector<pair<int,int> > E[maxn];
19 
20 int n,m;
21 int d[maxn];
22 
23 void init(){
24     for(int i=0; i<maxn; i++) E[i].clear();
25     for(int i=0; i<maxn; i++) d[i] = 1e9;
26 }
27 
28 int main(){
29     while(cin >> n >> m){
30         init();
31         for(int i=0; i<m; i++){
32             int u,v,w; scanf("%d%d%d",&u,&v,&w);
33             E[u].push_back(MP(v,w));
34             E[v].push_back(MP(u,w));
35         }
36 
37         int s,t;
38         scanf("%d%d",&s,&t);
39 
40         priority_queue<pair<int,int> > Q;
41         d[s]=0;
42         Q.push(MP(-d[s],s));
43         while(!Q.empty()){
44             int now = Q.top().second;
45             Q.pop();
46             for(int i=0; i<(int)E[now].size(); i++){
47                 int v = E[now][i].first, w = E[now][i].second;
48                 if(d[now]+w < d[v]){
49                     d[v] = d[now]+w;
50                     Q.push(MP(-d[v],v));
51                 }
52             }
53         }
54 
55         if(d[t] == 1e9) printf("-1
");
56         else printf("%d
",d[t]);
57     }
58 
59     return 0;
60 }