输入样例
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
输出样例
10
样例分析:
该样例中2是聚餐地, 4 号奶牛的总时间是:3+3+4=10; 3号奶牛的总时间是:2+4+1+2=9; 1号奶牛的总时间是4+1 = 5. 所以最长的时间是10
题目的大意是N个农场母牛要去一个农场参加母牛聚会,农场之间存在着路径.求去时和回来所用时间之和的最大值.而且母牛选取的都是最短路径.
思路:母牛去的目的地和母牛回来时的出发地都是聚会点.
去时:我们把母牛去时的路线进行反向建图,那么可以看做,母牛从目的地到各个点进行前进,符合单原路径问题
回来时: 我们进行正向建图,那么母牛从聚会点到各个农场也是个单原路径问题.
这个题中的数据量较大,我们最好使用SPFA.所以思路也就很明确了.
参考代码
#include<iostream> #include<string.h> #include<queue> using namespace std; const int maxn = 10000;//注意范围哦 int head[maxn],rhead[maxn], vis[maxn],dis[maxn],rdis[maxn],num,rnum;//rdis:反向图的 dis struct Edge{ int next,to,w; }e[maxn],re[maxn]; void add(int u,int v,int w,int &number,Edge *e,int *head){ e[++number].next = head[u]; e[number].to = v; e[number].w = w; head[u] = number; } void spfa(Edge *e,int *head,int u,int *dis){ queue<int> q;//数据的初始化 memset(vis,0,sizeof(vis)); memset(dis,0x3f,maxn*sizeof(int));//我们传进来的是指针,索引我们不能直接用 sizeof(head),这样是毫无意义的. q.push(u); vis[u] = 1; dis[u] = 0; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = head[x]; i; i=e[i].next){ if(dis[e[i].to] > dis[x]+e[i].w){ dis[e[i].to] = dis[x]+e[i].w; if(!vis[e[i].to]){ q.push(e[i].to); vis[e[i].to] = 1; } } } } } int main() { int n,m,x,u,v,t; long long ans = 0; cin>>n>>m>>x; while(m--){ cin>>u>>v>>t; add(u,v,t,num,e,head); add(v,u,t,rnum,re,rhead); } spfa(e,head,x,dis); spfa(re,rhead,x,rdis); for(int i = 1; i <= n; i++){ ans = max(ans,(long long)dis[i]+rdis[i]); } cout<<ans<<endl; return 0; }
注意:
函数参数为数组时,既可以使用指针进行传递也可以使用数组名[] 进行参数传递.(引用没试过)
memset进行初始化时是按照字节进行初始化的,所以对于整形数组进行初始化,如 初始化为正无穷INF, memset(arr,0x3f,sizeof(arr)) 如果传递的参数是指针,就不能使用sizeof了.
