「BZOJ1631」[Usaco2007 Feb] Cow Party
Description
农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？
Input
第1行:三个用空格隔开的整数.
第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
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求出终点到每个点/每个点到终点的距离。。。取个和的最小值
然后没了。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define mod 1000000009 #define ll long long #define inf 0x7fffffff using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,X,cnt,mx; int u[100005],v[100005],w[100005]; int q[1005],dis[1005],head[1005],ans[1005]; bool inq[1005]; struct edge{int to,next,v;}e[100005]; void insert(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} void spfa(int x) { memset(dis,127,sizeof(dis)); int t=0,w=1; q[t]=x;dis[x]=0;inq[x]=1; while(t!=w) { int now=q[t];t++;if(t==1001)t=0; for(int i=head[now];i;i=e[i].next) if(dis[now]+e[i].v<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]) {inq[e[i].to]=1;q[w++]=e[i].to;if(w==1001)w=0;} } inq[now]=0; } } int main() { n=read(),m=read(),X=read(); for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),w[i]=read(); for(int i=1;i<=m;i++) insert(u[i],v[i],w[i]); for(int i=1;i<=n;i++) {spfa(i);ans[i]=dis[X];} spfa(X); for(int i=1;i<=n;i++) mx=max(mx,dis[i]+ans[i]); printf("%d",mx); return 0; } |
计数器 9787641
OI 课件=>
OI 课件=>
请问spfa中存储用来更新其他结点的循环队列应该开多大？
点数咯