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

题目链接:

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

题意:

题解:

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

代码:

spfa：

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 205+10; std::vector<pair<int,int> > E[maxn]; int n,m; int d[maxn],inq[maxn]; void init(){ for(int i=0; i<maxn; i++) E[i].clear(); for(int i=0; i<maxn; i++) inq[i] = 0; for(int i=0; i<maxn; i++) d[i] = 1e9; } int main(){ while(cin >> n >> m){ init(); for(int i=0; i<m; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); E[u].push_back(MP(v,w)); E[v].push_back(MP(u,w)); } int s,t; scanf("%d%d",&s,&t); queue<int> Q; Q.push(s), d[s]=0, inq[s]=0; while(!Q.empty()){ int now = Q.front(); Q.pop(); inq[now] = 0; for(int i=0; i<(int)E[now].size(); i++){ int v = E[now][i].first, w = E[now][i].second; if(d[now]+w < d[v]){ d[v] = d[now]+w; if(inq[v]==1) continue; inq[v] = 1; Q.push(v); } } } if(d[t] == 1e9) printf("-1\n"); else printf("%d\n",d[t]); } return 0; }

dij：

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 205+10; std::vector<pair<int,int> > E[maxn]; int n,m; int d[maxn]; void init(){ for(int i=0; i<maxn; i++) E[i].clear(); for(int i=0; i<maxn; i++) d[i] = 1e9; } int main(){ while(cin >> n >> m){ init(); for(int i=0; i<m; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); E[u].push_back(MP(v,w)); E[v].push_back(MP(u,w)); } int s,t; scanf("%d%d",&s,&t); priority_queue<pair<int,int> > Q; d[s]=0; Q.push(MP(-d[s],s)); while(!Q.empty()){ int now = Q.top().second; Q.pop(); for(int i=0; i<(int)E[now].size(); i++){ int v = E[now][i].first, w = E[now][i].second; if(d[now]+w < d[v]){ d[v] = d[now]+w; Q.push(MP(-d[v],v)); } } } if(d[t] == 1e9) printf("-1\n"); else printf("%d\n",d[t]); } return 0; }