生活随笔
收集整理的这篇文章主要介绍了
POJ--3268--Silver Cow Party【SPFA+邻接表】
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题意：一些牛要去某一点參加聚会，然后再回到自己家，路是单向的，问花费时间最多的那头牛最少须要花费多长时间。
思路：从聚会地点返回，相当于是从某一点到其它各个点的最短路径。从牛的家中走到聚会地点，能够把路径反过来变成从聚会地点到各个点的最短路径，两个最短路径值加起来就是每头牛所花费的最小时间，找出最大的就可以。
我用了两个邻接表存路径，事实上这道题用邻接矩阵存更好做，矩阵横纵坐标翻转就把路径反转了，我用SPFA写想练练手，一直都不会手写SPFA，做几道题找找感觉。
AC竟然用时0MS。。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1struct node{int u,v,next;
}edge[MAXN],redge[MAXN];
int head[MAXN],rhead[MAXN],dist[MAXN],vis[MAXN],ans[MAXN];
int cnt,rcnt,n,m,x;
void add_edge(int a,int b,int c){edge[cnt].u = b;edge[cnt].v = c;edge[cnt].next = head[a];head[a] = cnt++;redge[rcnt].u = a;redge[rcnt].v = c;redge[rcnt].next = rhead[b];rhead[b] = rcnt++;
}
void spfa(int type){int i,j;for(i=1;i<=n;i++){dist[i] = INF;}dist[x] = 0;memset(vis,0,sizeof(vis));vis[x] = 1;queue<int>q;q.push(x);while(!q.empty()){int temp = q.front();q.pop();vis[temp] = 0;for(i=type?rhead[temp]:head[temp];i!=-1;i=type?redge[i].next:edge[i].next){int lu = type?redge[i].v:edge[i].v;if(lu+dist[temp]<dist[type?redge[i].u:edge[i].u]){dist[type?redge[i].u:edge[i].u] = lu + dist[temp];if(!vis[type?redge[i].u:edge[i].u]){vis[type?redge[i].u:edge[i].u] = 1;q.push(type?redge[i].u:edge[i].u);}}}}
}
int main(){int i,j,a,b,c;scanf("%d%d%d",&n,&m,&x);memset(head,-1,sizeof(head));memset(rhead,-1,sizeof(rhead));cnt = rcnt = 0;int maxm = 0;for(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);add_edge(a,b,c);}spfa(0);for(i=1;i<=n;i++){if(i!=x) ans[i] = dist[i];}spfa(1);for(i=1;i<=n;i++){if(i!=x) ans[i] += dist[i];if(ans[i]>maxm) maxm = ans[i];}printf("%d\n",maxm);return 0;
}
总结
以上是生活随笔为你收集整理的POJ--3268--Silver Cow Party【SPFA+邻接表】的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
