BZOJ 1631: [Usaco2007 Feb]Cow Party
Description 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共
有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？ Input 第1行:三个用空格隔开的整数.
【BZOJ 1631: [Usaco2007 Feb]Cow Party】 第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.
Output 唯一一行:一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.
Sample Input 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
Sample Output 10
HINT
样例说明:
共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.
第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.
题解
spfa水过。
#include
#include
#include
#include
#include
#include
#define inf 1<<30
using namespace std;
int n,m,S,zz,head[1005];
struct bian{int to,nx,v;
} e[100005];
int dis[1005],pd[1005],q[1005],ans[1005];
void insert(int x,int y,int z)
{zz++;
e[zz].to=y;
e[zz].v=z;
e[zz].nx=head[x];
head[x]=zz;
}
void init()
{
scanf("%d%d%d",&n,&m,&S);
int i,x,y,z;
for(i=1;
i<=m;
i++)
{scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
}
}
void spfa(int x)
{
int t=0,w=1,i,p;
for(i=1;
i<=n;
i++) dis[i]=inf;
q[t]=x;
pd[x]=1;
dis[x]=0;
while(t!=w)
{p=q[t];
t=(t+1)%n;
for(i=head[p];
i;
i=e[i].nx)
{if(dis[e[i].to]>dis[p]+e[i].v)
{dis[e[i].to]=dis[p]+e[i].v;
if(!pd[e[i].to])
{pd[e[i].to]=1;
q[w]=e[i].to;
w=(w+1)%n;
}
}
}
pd[p]=0;
}
}
void work()
{
int i,mx=0;
for(i=1;
i<=n;
i++) {spfa(i);
ans[i]=dis[S];
}
spfa(S);
for(i=1;
i<=n;
i++)
mx=max(mx,ans[i]+dis[i]);
printf("%d\n",mx);
}
int main()
{
init();
work();
return 0;
} 推荐阅读
- Python日志_20211019_1631
- 【BZOJ】4316:|【BZOJ】4316: 小C的独立集 静态仙人掌
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- bzoj|Bzoj3817:Sum
- BZOJ|BZOJ2763[JLOI2011]飞行路线【分层图最短路】
- BZOJ3817（Sum（类欧几里得））
- 类欧几里得|bzoj2987 Earthquake 类欧几里得
- 题解|[BZOJ3817] Sum
- bzoj2712 -- 类欧几里得算法