首页 > 代码库 > poj 3268 Silver Cow Party , spfa , dijkstra
poj 3268 Silver Cow Party , spfa , dijkstra
点击打开链接
两次求最短路(第二次把边反向求)
1、spfa
//poj 3268 Silver Cow Party //SPFA #include <cstdio> #include <cstring> #include <queue> using namespace std; const int M = 100000 + 100; const int N = 1000 + 100; const int inf = 1<<25; struct Graph { int head[N], next[M], to[M], val[M], cnt, n; void init(int num) { memset(head, -1, sizeof head ); for(int i=1; i<=n; ++i) d[i] = inf; cnt = 0; n = num; while(!q.empty()) q.pop(); } void addedge(int u, int v, int c) { next[cnt] = head[u]; to[cnt] = v; val[cnt] = c; head[u ] = cnt++; } int d[N], vis[M]; queue<int> q; void spfa(int s) { memset(vis, 0, sizeof vis ); d[s] = 0; vis[s] = 1; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i=head[u]; ~i; i = next[i]) { int v = to[i]; if(d[v] > d[u] + val[i]) { d[v] = d[u] + val[i]; if(!vis[v]) { vis[v] = 1; q.push(v); } } } vis[u] = 0; } } } g1, g2; int n, m, x; int main() { while(~scanf("%d%d%d", &n, &m, &x)) { g1.init(n); g2.init(n); int u, v, c; for(int i=1; i<=m; ++i){ scanf("%d%d%d", &u, &v, &c); g1.addedge(u, v, c); g2.addedge(v, u, c); } g1.spfa(x); g2.spfa(x); int ans = 0; for(int i=1; i<=n; ++i) { if(i != x) { if(g1.d[i] != inf && g2.d[i] != inf) { if(ans < g1.d[i] + g2.d[i]) ans = g1.d[i] + g2.d[i]; } } } printf("%d\n", ans); } return 0; }
2、dijkstra
#include <cstdio>#include <cstring>#include <queue>using namespace std;const int M = 100000 + 100;const int N = 1000 + 100;const int inf = 1<<25;typedef pair<int, int> P;int n, m, x;struct node { int v; int c; node(int vv=0, int cc=0): v(vv), c(cc) {} /* bool operator < (const node& r) const { return c > r.c; } */};struct Graph{ int head[N], next[M], to[M], val[M], cnt, n; void init(int nv) { memset(head, -1, sizeof head ); n = nv; for(int i=1; i<=n; ++i) d[i] = inf; cnt = 0; while(!q.empty()) q.pop(); } void addedge(int u, int v, int c) { next[cnt] = head[u]; to[cnt] = v; val[cnt] = c; head[u] = cnt++; } int d[N]; priority_queue<P, vector<P>, greater<P> > q; void dijkstra(int s) { d[s] = 0; q.push(P(0,s)); while(!q.empty()){ P p = q.top(); q.pop(); int v = p.second; if(d[v]<p.first) continue; for(int i=head[v]; ~i; i =next[i]) { int k = to[i]; if(d[k] > d[v] + val[i]) { d[k] = d[v] + val[i]; q.push(P(d[k], k)); } } } }}s1, s2;int main(){ int u, v, c; scanf("%d%d%d", &n, &m, &x); s1.init(n); s2.init(n); for(int i=1; i<=m; ++i) { scanf("%d%d%d", &u, &v, &c); s1.addedge(u, v, c); s2.addedge(v, u, c); } s1.dijkstra(x); s2.dijkstra(x); int ans = 0; for(int i=1; i<=n; ++i) { if(i==x) continue; if(s1.d[i] + s2.d[i] > ans) ans = s1.d[i] + s2.d[i]; } printf("%d\n", ans); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。