USACO-银牛派对

Author Avatar
ZC 10月 08, 2018
  • 在其它设备中阅读本文章

题目描述

寒假到了,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

题解:

的确是水题。

只要跑最短路时建正、反向图就可以了

代码:

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define in2(x,y) in(x),in(y)
    #define in3(x,y,z) in2(x,y),in(z)
    #define in4(a,b,c,d) in2(a,b);in2(c,d)
    #define outn(x) out(x),pc('\n')
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 2147483630
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define gt io.gc()
    #define l2(n) (log(n)/log(2))
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
    MB il void SWAP(T x,T y){T t=x;y=t;x=y;}
}using namespace ZDY;using namespace std;

class IO{
   #define fok (ch!=EOF)
   #define sep (ch==' '||ch=='\n'||ch=='\t')
   #define dsep !isdigit(ch)
   #define neq(a,b) ((a)-(b)>1e-6)
   char rbuf[1<<20],wbuf[1<<20],b,*p1,*p2;
   int rs,ws,S;
   public:
       IO():p1(rbuf),p2(wbuf),S(1000000),rs(1000000),ws(-1),b(1){}
       ~IO(){fwrite(wbuf,1,ws+1,stdout);}
       il char gc(){return rs==S&&(p1=rbuf,rs=-1,(S=fread(rbuf,1,S+1,stdin)-1)==-1)?(b=0,EOF):(++rs,*p1++);}
       il void pc(int x){ws==1000000&&(p2=wbuf,ws=-1,fwrite(wbuf,1,1000001,stdout)),++ws,*p2++=x;}
       il void puts(const char str[]){fwrite(wbuf,1,ws+1,stdout)?(ws=-1):0,fwrite(str,1,strlen(str),stdout);}
       il void gl(string& s){for(res char ch;(ch=gc())!='\n'&&fok;)s+=ch;}
       il IO& operator>>(int& x){x=0;res char f=0,ch=gc();while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();return x=f?-x:x,*this;}
       il IO& operator>>(ll& x){x=0;res char f=0,ch=gc();while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();return x=f?-x:x,*this;}
       il IO& operator>>(char& ch){return ch=gc(),*this;}
       il IO& operator>>(string& s){res char ch=gc();while(sep&&fok)ch=gc();while(!sep&&fok)s+=ch,ch=gc();return *this;}
       il IO& operator>>(double& x){x=0;res char f=0,ch=gc();double d=0.1;while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=x*10+(ch^48),ch=gc();if(ch=='.')while(isdigit(ch=gc()))x+=d*(ch^48),d*=0.1;return x=f?-x:x,*this;}
       il IO& operator<<(int x){res char ch[10],i=-1;!x?(pc('0'),0):0,x<0?(pc('-'),x=-x):0;while(x)ch[++i]=x%10+48,x/=10;while(~i)pc(ch[i]),--i;return *this;}
       il IO& operator<<(ll x){res char ch[20],i=-1;!x?(pc('0'),0):0,x<0?(pc('-'),x=-x):0;while(x)ch[++i]=x%10+48,x/=10;while(~i)pc(ch[i]),--i;return *this;}
       il IO& operator<<(char ch){return pc(ch),*this;}
       il IO& operator<<(char str[]){return puts(str),*this;}
       il IO& operator<<(double x){int y=int(x);*this<<y;x-=y;while(neq(x,int(x)))x*=10;x?*this<<'.'<<int(x):0;return *this;}
       il operator bool(){return b;}
}io;

#define N 1001
int n,m,s,cnt,CNT,d[N],D[N],head[N],HEAD[N];
bool v[N];
struct edge{int to,w,nxt;}e[100001],E[100001];
#define FL(i,x) for(ri i=HEAD[x],to;to=E[i].to,i;i=E[i].nxt)
struct cmp{bool operator()(int a,int b){return d[a]>d[b];}};
priority_queue<int,vector<int>,cmp>q;
il void add(int x,int y,int w){e[++cnt].to=y;e[cnt].w=w;e[cnt].nxt=head[x];head[x]=cnt;}
il void ADD(int x,int y,int w){E[++CNT].to=y;E[CNT].w=w;E[CNT].nxt=HEAD[x];HEAD[x]=CNT;}
il void spfa(){
    clr(d,126);clr(D,126);
    d[s]=D[s]=0;q.push(s);
    int x;
    while(!q.empty()){
        v[x=q.top()]=0;q.pop();
        fl(i,x)
        if(d[x]+e[i].w<d[to]){
            d[to]=d[x]+e[i].w;
            if(!v[to])q.push(to),v[to]=1;
        }
        FL(i,x)
        if(D[x]+E[i].w<D[to]){
            D[to]=D[x]+E[i].w;
            if(!v[to])q.push(to),v[to]=1;
        }
    }
}
int main(){
    io>>n>>m>>s;
    int x,y,w,ans=0;
    Fur(i,1,m)io>>x>>y>>w,add(x,y,w),ADD(y,x,w);
    spfa();
    Fur(i,1,n)ans=MAX(ans,d[i]+D[i]);
    io<<ans<<'\n';
}

彩蛋:

双倍经验题:LUOGU P1629 邮递员送信

(把所有最大值改成所有总和就可以了)

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define in2(x,y) in(x),in(y)
    #define in3(x,y,z) in2(x,y),in(z)
    #define in4(a,b,c,d) in2(a,b);in2(c,d)
    #define outn(x) out(x),pc('\n')
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 2147483630
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define gt io.gc()
    #define l2(n) (log(n)/log(2))
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
    MB il void SWAP(T x,T y){T t=x;y=t;x=y;}
}using namespace ZDY;using namespace std;

class IO{
   #define fok (ch!=EOF)
   #define sep (ch==' '||ch=='\n'||ch=='\t')
   #define dsep !isdigit(ch)
   #define neq(a,b) ((a)-(b)>1e-6)
   char rbuf[1<<20],wbuf[1<<20],b,*p1,*p2;
   int rs,ws,S;
   public:
       IO():p1(rbuf),p2(wbuf),S(1000000),rs(1000000),ws(-1),b(1){}
       ~IO(){fwrite(wbuf,1,ws+1,stdout);}
       il char gc(){return rs==S&&(p1=rbuf,rs=-1,(S=fread(rbuf,1,S+1,stdin)-1)==-1)?(b=0,EOF):(++rs,*p1++);}
       il void pc(int x){ws==1000000&&(p2=wbuf,ws=-1,fwrite(wbuf,1,1000001,stdout)),++ws,*p2++=x;}
       il void puts(const char str[]){fwrite(wbuf,1,ws+1,stdout)?(ws=-1):0,fwrite(str,1,strlen(str),stdout);}
       il void gl(string& s){for(res char ch;(ch=gc())!='\n'&&fok;)s+=ch;}
       il IO& operator>>(int& x){x=0;res char f=0,ch=gc();while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();return x=f?-x:x,*this;}
       il IO& operator>>(ll& x){x=0;res char f=0,ch=gc();while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();return x=f?-x:x,*this;}
       il IO& operator>>(char& ch){return ch=gc(),*this;}
       il IO& operator>>(string& s){res char ch=gc();while(sep&&fok)ch=gc();while(!sep&&fok)s+=ch,ch=gc();return *this;}
       il IO& operator>>(double& x){x=0;res char f=0,ch=gc();double d=0.1;while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=x*10+(ch^48),ch=gc();if(ch=='.')while(isdigit(ch=gc()))x+=d*(ch^48),d*=0.1;return x=f?-x:x,*this;}
       il IO& operator<<(int x){res char ch[10],i=-1;!x?(pc('0'),0):0,x<0?(pc('-'),x=-x):0;while(x)ch[++i]=x%10+48,x/=10;while(~i)pc(ch[i]),--i;return *this;}
       il IO& operator<<(ll x){res char ch[20],i=-1;!x?(pc('0'),0):0,x<0?(pc('-'),x=-x):0;while(x)ch[++i]=x%10+48,x/=10;while(~i)pc(ch[i]),--i;return *this;}
       il IO& operator<<(char ch){return pc(ch),*this;}
       il IO& operator<<(char str[]){return puts(str),*this;}
       il IO& operator<<(double x){int y=int(x);*this<<y;x-=y;while(neq(x,int(x)))x*=10;x?*this<<'.'<<int(x):0;return *this;}
       il operator bool(){return b;}
}io;

#define N 1001
int n,m,cnt,CNT,d[N],D[N],head[N],HEAD[N];
bool v[N];
struct edge{int to,w,nxt;}e[100001],E[100001];
#define FL(i,x) for(ri i=HEAD[x],to;to=E[i].to,i;i=E[i].nxt)
struct cmp{bool operator()(int a,int b){return d[a]>d[b];}};
priority_queue<int,vector<int>,cmp>q;
il void add(int x,int y,int w){e[++cnt].to=y;e[cnt].w=w;e[cnt].nxt=head[x];head[x]=cnt;}
il void ADD(int x,int y,int w){E[++CNT].to=y;E[CNT].w=w;E[CNT].nxt=HEAD[x];HEAD[x]=CNT;}
il void spfa(){
    clr(d,126);clr(D,126);
    d[1]=D[1]=0;q.push(1);
    int x;
    while(!q.empty()){
        v[x=q.top()]=0;q.pop();
        fl(i,x)
        if(d[x]+e[i].w<d[to]){
            d[to]=d[x]+e[i].w;
            if(!v[to])q.push(to),v[to]=1;
        }
        FL(i,x)
        if(D[x]+E[i].w<D[to]){
            D[to]=D[x]+E[i].w;
            if(!v[to])q.push(to),v[to]=1;
        }
    }
}
int main(){
    io>>n>>m;
    int x,y,w,ans=0;
    Fur(i,1,m)io>>x>>y>>w,add(x,y,w),ADD(y,x,w);
    spfa();
    Fur(i,2,n)ans+=d[i]+D[i];
    io<<ans<<'\n';
}