題目描述

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

寒假到了，N頭牛都要去參加一場在編號為X（1≤X≤N）的牛的農場舉行的派對（1≤N≤1000），農場之間有M（1≤M≤100000）條有向路，每條路長Ti（1≤Ti≤100）。

每頭牛參加完派對后都必須回家，無論是去參加派對還是回家，每頭牛都會選擇最短路徑，求這N頭牛的最短路徑（一個來回）中最長的一條路徑長度。

輸入輸出格式

輸入格式：

?

第一行三個整數N，M, X；

第二行到第M+1行：每行有三個整數Ai，Bi, Ti ,表示有一條從Ai農場到Bi農場的道路，長度為Ti。

?

輸出格式：

?

一個整數，表示最長的最短路得長度。

?

輸入輸出樣例

輸入樣例#1：? 復制 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 輸出樣例#1：? 復制 10

說明

題解：正反兩個方向建圖，跑兩遍SPFA即可。

#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int oo=0x3f3f3f3f; int n,m,x,y,z,kun; int d1[100005],vis[100005]; int d2[100005]; struct node{int to;int next;int val; }e1[100005]; node e2[100005]; int h1[100005]; int h2[100005]; int cnt1,cnt2; void add(int a,int b,int c){cnt1++;e1[cnt1].to=b;e1[cnt1].val=c;e1[cnt1].next=h1[a];h1[a]=cnt1;cnt2++;e2[cnt2].to=a;e2[cnt2].val=c;e2[cnt2].next=h2[b];h2[b]=cnt2; }void cai(){queue<int>q;memset(vis,0,sizeof(vis));//memset(q,0,sizeof(q)); q.push(kun);d1[kun]=0;vis[kun]=1;while(!q.empty()){x=q.front();q.pop();vis[x]=0;for(int i=h1[x];i;i=e1[i].next){int v=e1[i].to;if(d1[v]>d1[x]+e1[i].val){d1[v]=d1[x]+e1[i].val;if(vis[v]==0){q.push(v);vis[v]=1;}}}} }void xu(){queue<int>q;memset(vis,0,sizeof(vis));//memset(q,0,sizeof(q)); q.push(kun);d2[kun]=0;vis[kun]=1;while(!q.empty()){x=q.front();q.pop();vis[x]=0;for(int i=h2[x];i;i=e2[i].next){int v=e2[i].to;if(d2[v]>d2[x]+e2[i].val){d2[v]=d2[x]+e2[i].val;if(vis[v]==0){q.push(v);vis[v]=1;}}}} } int main(){freopen("1821.in","r",stdin);freopen("1821.out","w",stdout);scanf("%d %d %d",&n,&m,&kun);for(int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&z);add(x,y,z); }for(int i=1;i<=n;i++)d1[i]=d2[i]=oo;cai(); xu();int ans=0;for(int i=1;i<=n;i++)ans=max(ans,d1[i]+d2[i]);printf("%d",ans);/*int mx=0;int id=0;for(int i=1;i<=n;i++)if(d2[i]>mx){ mx=d2[i]; id=i; } printf("%d %d ",id,mx);int ans=0;for(int i=1;i<=n;i++)ans+=(mx==d2[i]);printf("%d",ans);*/return 0; }

?

轉載于:https://www.cnblogs.com/wuhu-JJJ/p/11178996.html

總結

以上是生活随笔為你收集整理的【洛谷 1821】银牛派对Silver Cow Party的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。