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

2019-11-06 07:16:57

字体：大中小

来源：转载

供稿：网友

题目链接:

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_backconst 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_backconst 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;}

上一篇：【Activiti工作流】6.Activiti入门程序HelloWorld演示流程的执行(下)

下一篇：poj 2406 Power Strings(KMP）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注