神秘字典序最短路

Frank2010 · 2025-07-03 19:37:58 · 个人记录

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=10005,M=50005;
inline int read(){
    char c=getchar();
    bool flag=false;
    while(!isdigit(c)){
        if(c=='-')flag=true;
        c=getchar();
    }
    int x=0;
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return flag?-x:x;
}
int n,m,t,c[N],a,b,d,k,pre[N],dis[N],cnt[N];
struct edge{
    int v,w,next;
}e[M<<1];
void add(int u,int v,int w){
    e[++k]={v,w,pre[u]};
    pre[u]=k;
}
struct node{
    int v,w;
    bool operator<(const node&x)const{
        return x.w<w;
    }
};
bool vis[N];
deque<int>v[N];
void dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<node>p;
    p.push({s,0});
    v[s].emplace_front(s);
    while(!p.empty()){
        int u=p.top().v;
        p.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(int i=pre[u];i;i=e[i].next){
            if(dis[u]+e[i].w<dis[e[i].v]){
                dis[e[i].v]=dis[u]+e[i].w;
                p.push({e[i].v,dis[e[i].v]});
                v[e[i].v]=v[u];
                v[e[i].v].emplace_front(e[i].v);
            }
            else if(dis[u]+e[i].w==dis[e[i].v]){
                auto tv=v[u];
                tv.emplace_front(e[i].v);
                if(tv<v[e[i].v]){
                    v[e[i].v]=v[u];
                    v[e[i].v].emplace_front(e[i].v);
                }
            }
        }
    }
}
long long ans;
int main(){
    //freopen("meow.in","r",stdin);
    //freopen("meow.out","w",stdout);
    n=read();
    m=read();
    t=read();
    for(int i=1;i<=n;i++)c[i]=read();
    while(m--){
        a=read();
        b=read();
        d=read();
        add(a,b,d);
        add(b,a,d);
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)for(int j:v[i])cnt[j]+=c[i];
    for(int i=2;i<=n;i++)ans=max(ans,(dis[i]-t)*1LL*cnt[i]);
    printf("%lld",ans);
    return 0;
}