題目描述

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頭牛都要去參加一場(chǎng)在編號(hào)為X（1≤X≤N）的牛的農(nóng)場(chǎng)舉行的派對(duì)（1≤N≤1000），農(nóng)場(chǎng)之間有M（1≤M≤100000）條有向路，每條路長(zhǎng)Ti（1≤Ti≤100）。

每頭牛參加完派對(duì)后都必須回家，無(wú)論是去參加派對(duì)還是回家，每頭牛都會(huì)選擇最短路徑，求這N頭牛的最短路徑（一個(gè)來(lái)回）中最長(zhǎng)的一條路徑長(zhǎng)度。

輸入輸出格式

輸入格式：

?

第一行三個(gè)整數(shù)N，M, X；

第二行到第M+1行：每行有三個(gè)整數(shù)Ai，Bi, Ti ,表示有一條從Ai農(nóng)場(chǎng)到Bi農(nóng)場(chǎng)的道路，長(zhǎng)度為Ti。

?

輸出格式：

?

一個(gè)整數(shù)，表示最長(zhǎng)的最短路得長(zhǎng)度。

?

輸入輸出樣例

輸入樣例#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
兩次Dijkstra
屠龍寶刀點(diǎn)擊就送
#include <algorithm> #include <cstring> #include <cstdio>#define over() return 0; #define inf 0x7fffffff using namespace std;bool vis[1001]; int Answer=-0x7fffffff,n,m,i,j,dis1[1001],dis2[1001],atlas[1001][1001]; int min(int a,int b) {return a>b?b:a; } void Dijkstra1(int start) {for(i=1;i<=n;++i){dis1[i]=atlas[start][i];vis[i]=0;}vis[start]=1;dis1[start]=0;for(i=1;i<n;++i){int minx=inf,to;for(j=1;j<=n;++j){if(!vis[j]&&minx>dis1[j]){minx=dis1[j];to=j;}}vis[to]=1;for(j=1;j<=n;++j){if(dis1[j]>dis1[to]+atlas[to][j])dis1[j]=dis1[to]+atlas[to][j];}} }void Dijkstra2(int start) {for(i=1;i<=n;++i){dis2[i]=atlas[start][i];vis[i]=0;}vis[start]=1;dis2[start]=0;for(i=1;i<n;++i){int minx=inf,to;for(j=1;j<=n;++j){if(!vis[j]&&minx>dis2[j]){minx=dis2[j];to=j;}}vis[to]=1;for(j=1;j<=n;++j){if(dis2[j]>dis2[to]+atlas[to][j])dis2[j]=dis2[to]+atlas[to][j];}} } int main() {int x;scanf("%d%d%d",&n,&m,&x);int u[100001],v[100001],l[100001];memset(atlas,1,sizeof(atlas));for(i=1;i<=m;++i){scanf("%d%d%d",&u[i],&v[i],&l[i]);atlas[u[i]][v[i]]=min(atlas[u[i]][v[i]],l[i]);}Dijkstra1(x);memset(atlas,1,sizeof(atlas));for(i=1;i<=m;++i)atlas[v[i]][u[i]]=min(atlas[v[i]][u[i]],l[i]);Dijkstra2(x);for(i=2;i<=n;++i)Answer=Answer>dis1[i]+dis2[i]?Answer:dis1[i]+dis2[i];printf("%d",Answer);over() }

轉(zhuǎn)載于:https://www.cnblogs.com/ruojisun/p/6445726.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1821 [USACO07FEB]银牛派对Silver Cow Party的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。