1631: [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
Sample Output
10
HINT
样例说明:
共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.
第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.
Source
Silver

SPFA

#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;
}

自己的代码改了半天最后发现是数组开小了。。。。。。。。。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define inf 10000000
#define maxn 1010
#define maxm 100010
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
#define for5(i,x) for(int i=head1[x],y=e1[i].go;i;i=e1[i].next,y=e1[i].go)
using namespace std;
int n,m,s;
int d[maxn],d1[maxn];
bool v[maxn],v1[maxn];
int tot,tot1;
int head[maxn],head1[maxn];
queue<int>q;
struct edge{int go,next,w;}e[maxm],e1[maxm];
inline void add(int x,int y,int w)
{
    e[++tot]=(edge){y,head[x],w};head[x]=tot;
    e1[++tot1]=(edge){x,head1[y],w};head1[y]=tot1;
}
int main()
{
	memset(head,0,sizeof(head));
	freopen("sparty.in","r",stdin);
	freopen("sparty.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
    for1(i,m){
    	int a,b,c;
    	scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
    for1(i,n)d[i]=inf,d1[i]=inf;
    d[s]=0;q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();v[x]=0;
        for4(i,x)if(d[x]+e[i].w<d[y])
        {
            d[y]=d[x]+e[i].w;
            if(!v[y]){v[y]=1;q.push(y);}
        }
    }
    d1[s]=0;q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();v1[x]=0;
        for5(i,x)if(d1[x]+e1[i].w<d1[y])
        {
            d1[y]=d1[x]+e1[i].w;
            if(!v1[y]){v1[y]=1;q.push(y);}
        }
    }
    int ans=0;
    for1(i,n)ans=max(ans,d[i]+d1[i]);
    cout<<ans<<endl;
    return 0;
}

 

此条目发表在BZOJ, SPFA, USACO, 最短路分类目录。将固定链接加入收藏夹。