LG5201 「USACO2019JAN」Shortcut 最短路树

\(\mathrm{Shortcut}\)

问题描述

LG5201

题解

最短路树。

显然奶牛的路径就是从\(1\)走到各个草地，于是从\(1\)跑最短路，构建最短路树。

为了保证字典序，从\(1\)到\(n\)依次枚举每个结点，构建。

显然，用贪心的思想，这条边一定是从某个结点\(x\)联向\(1\)的。

然后深度遍历这棵最短路树，在每个结点处处理答案即可。

注意需要long long

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template<typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

#define int long long

const int maxn=10000+7;
const int maxm=100000+7;
const int INF=0x3f3f3f3f3f3f3f3fLL;

int n,m,t;
int cows[maxn];

int u[maxm],Head[maxn],Next[maxm],to[maxm],w[maxm],tot=1;

struct node{
    int id,dis;
    bool operator <(node a)const{
        return dis>a.dis;
    }
};

void add(int x,int y,int z){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z,u[tot]=x;
}

int Jead[maxn],Mext[maxm],of[maxm],fork=1;

void fafa(int x,int y){
    of[++fork]=y,Mext[fork]=Jead[x],Jead[x]=fork;
}

int dis[maxn];
bool vis[maxn];
void dijkstra(){
    for(int i=2;i<=n;i++) dis[i]=INF;
    priority_queue<node>q;
    q.push(node{1,0});dis[1]=0;
    while(!q.empty()){
        int x=q.top().id;q.pop();
        if(vis[x]) continue;vis[x]=1;
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(dis[y]>dis[x]+w[i]){
                dis[y]=dis[x]+w[i];
                q.push((node){y,dis[y]});
            }
        }
    }
}

bool exist[maxn];

void build(){
    for(int x=1;x<=n;x++){
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(!exist[y]&&dis[y]==dis[x]+w[i]){
                fafa(x,y);fafa(y,x);exist[y]=1;
            }
        }
    }
}

bool ins[maxn];
int size[maxn],ans;

void dfs(int x){
    ins[x]=1,size[x]=cows[x];
    for(int i=Jead[x];i;i=Mext[i]){
        int y=of[i];
        if(!ins[y]){
            dfs(y);size[x]+=size[y];
        }
    }
    ans=max(ans,size[x]*(dis[x]-t));
}

void Init(){
    read(n);read(m);read(t);
    for(int i=1;i<=n;i++) read(cows[i]);
    for(int i=1,x,y,z;i<=m;i++){
        read(x);read(y);read(z);
        add(x,y,z);add(y,x,z);
    }
}

void Work(){
    dijkstra();
    build();
    dfs(1);
    printf("%lld\n",ans);
}

signed main(){
    freopen("shortcut.in","r",stdin);freopen("shortcut.out","w",stdout);
    Init();Work();
    fclose(stdin);fclose(stdout);
    return 0;
}