分析一下题目，考虑构建费用流模型（为什么会想到费用流啊！）
把每个点拆成两个 $u,v$
从 $v$ 到 $T$ 连一条流量为 $1$，费用为 $0$ 的边（这条边满流说明此点走完了）
从 $S$ 向每个点 $v$ 连一条流量为 $1$，费用为能力爆发到此星球的时间（从任何一点跳跃其实就相当于从原点重新开始）
从 $S$ 向每个点 $u$ 连一条流量为 $1$，费用为 $0$ 的边（因为每个点都要经过一次，所以每个点都会到达过）
从每个点的 $u$ 向此点连边到达的 $v$ 连一条流量为 $1$，费用为走此边需要的时间
然后最小费用最大流就是答案了...
为什么是对的呢，因为每个点都要被走过一次，所以一定要有某条到它的边是满流的，而上面这种连边方式就保证了所有可能连向它的边都被考虑到了
所以是对的...(大概)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,M=1e7+7,INF=1e9+7; int fir[N],from[M],to[M],val[M],cst[M],cntt=1; inline void add(int a,int b,int c,int d) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; cst[cntt]=d; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; cst[cntt]=-d; } int dis[N],mif[N],pre[N],S,T; queue <int> q; bool inq[N]; bool SPFA() { for(int i=S;i<=T;i++) dis[i]=INF; q.push(S); inq[S]=1; dis[S]=0,mif[S]=INF; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(!val[i]||dis[v]<=dis[x]+cst[i]) continue; dis[v]=dis[x]+cst[i]; pre[v]=i; mif[v]=min(mif[x],val[i]); if(!inq[v]) q.push(v),inq[v]=1; } } return dis[T]<INF; } ll ans; void upd() { for(int now=T,i=pre[T]; now!=S; now=to[i^1],i=pre[now]) val[i]-=mif[T],val[i^1]+=mif[T]; ans+=1ll*mif[T]*dis[T]; } int n,m; int main() { n=read(),m=read(); int a,b,c; S=0,T=(n<<1)+1; for(int i=1;i<=n;i++) add(S,n+i,1,read()),add(S,i,1,0),add(n+i,T,1,0); for(int i=1;i<=m;i++) { a=read(),b=read(),c=read(); if(a>b) swap(a,b); add(a,n+b,1,c); } while(SPFA()) upd(); printf("%lld",ans); return 0; }