henrytb 的博客

henrytb 的博客

题解 P3110 【[USACO14DEC]驮运Piggy Back】

posted on 2019-04-14 10:18:37 | under 题解 |

2922372513332~

水一发题解

这道题可以以B、E和谷仓为源点跑3遍最短路(SPFA或dijkstra),然后枚举B和E在哪一个点相遇后开始背,取最小值

呆码码风清奇:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=80005;
const int inf=0x3f3f3f3f;
int target[N],last[N],pre[N],tot,B,E,P,n,m,ans=inf;
int disb[N],dise[N],disn[N];
void add(int u,int v){
    target[++tot]=v;
    pre[tot]=last[u];
    last[u]=tot;
}
void spfa(int s,int *dis){
    rep(i,1,n)dis[i]=inf;
    int he=0,ta=1;
    int q[N],vis[N];
    rep(i,1,n)vis[i]=0;
    q[++he]=s;
    dis[s]=0;
    vis[s]=1;
    while(he<=ta){
        int u=q[he++];
        vis[u]=0;
        int ptr=last[u];
        while(ptr){
            int v=target[ptr];
            if(dis[u]+1<dis[v]){
                dis[v]=dis[u]+1;
                if(!vis[v])vis[v]=1,q[++ta]=v;
            }
            ptr=pre[ptr];
        }
    }
}
int main(){
    scanf("%d%d%d%d%d",&B,&E,&P,&n,&m);
    rep(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    spfa(1,disb);
    spfa(2,dise);
    spfa(n,disn);
    rep(i,1,n){
        ans=min(ans,B*disb[i]+E*dise[i]+P*disn[i]);
    }
    printf("%d",ans);
    return 0;
}