首页 > 代码库 > Poj 3268 Silver Cow Party
Poj 3268 Silver Cow Party
最短路水题,这次用SPFA写
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 1000 + 5;const int INF = INT_MAX / 2;const int maxm = 100000 + 5;int first[maxn],nxt[maxm],u[maxm],v[maxm],w[maxm];int N,M,X,d1[maxn],d2[maxn];bool vis[maxn];void spfa(int *v,int *d) { memset(vis,0,sizeof(vis)); for(int i = 1;i <= N;i++) d[i] = INF; d[X] = 0; queue<int> q; q.push(X); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = first[u];i != 0;i = nxt[i]) { if(d[v[i]] > d[u] + w[i]) { d[v[i]] = d[u] + w[i]; if(!vis[v[i]]) { vis[v[i]] = true; q.push(v[i]); } } } }}void adde(int u,int i) { nxt[i] = first[u]; first[u] = i;}int main() { while(scanf("%d%d%d",&N,&M,&X) != EOF) { memset(first,0,sizeof(first)); memset(nxt,0,sizeof(nxt)); for(int i = 1;i <= M;i++) { scanf("%d%d%d",&u[i],&v[i],&w[i]); adde(u[i],i); } spfa(v,d1); memset(first,0,sizeof(first)); memset(nxt,0,sizeof(nxt)); for(int i = 1;i <= M;i++) { adde(v[i],i); } spfa(u,d2); int ans = 0; for(int i = 1;i <= N;i++) ans = max(ans,d1[i] + d2[i]); printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。