这个没啥难的.
只保留可以转移最短路的边，然后拆点跑一个最大流即可.
#include <bits/stdc++.h>
#define N 1004
#define M 250004
#define ll long long
#define inf 200000000001
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int s,t,tot,n,m,eds;
int vis[N],current[N],id[N][2],hd[N],to[M],nex[M],val[M],cc[N],U[M],V[M],VAL[M];
void add(int u,int v,int c)
{
nex[++eds]=hd[u],hd[u]=eds,to[eds]=v,val[eds]=c;
}
struct Dijkstra
{
ll d[N];
int done[N];
struct Node
{
int u;
long long dis;
Node(int u=0,ll dis=0):u(u),dis(dis){}
bool operator<(Node b) const
{
return b.dis<dis;
}
};
priority_queue<Node>q;
void dijkstra(int aa)
{
memset(d,0x3f,sizeof(d));
for(d[aa]=0,q.push(Node(aa,0));!q.empty();)
{
Node e=q.top();q.pop();
int u=e.u;
if(done[u]) continue;
done[u]=1;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(d[v]>d[u]+val[i])
{
d[v]=d[u]+val[i];
q.push(Node(v, d[v]));
}
}
}
}
}S,T;
int d[M];
struct Edge
{
ll cap;
int u,v;
Edge(int u=0,int v=0,ll cap=0):u(u),v(v),cap(cap){}
};
queue<int>q;
vector<Edge>edges;
vector<int>G[N];
void addedge(int u,int v,ll c)
{
edges.push_back(Edge(u,v,c));
edges.push_back(Edge(v,u,0));
int p=edges.size();
G[u].push_back(p-2);
G[v].push_back(p-1);
}
int BFS()
{
memset(vis,0,sizeof(vis));
d[s]=0,q.push(s),vis[s]=1;
for(;!q.empty();)
{
int u=q.front(); q.pop();
for(int i=0;i<G[u].size();++i)
{
Edge e=edges[G[u][i]];
if(e.cap>0&&!vis[e.v])
{
vis[e.v]=1;
d[e.v]=d[u]+1;
q.push(e.v);
}
}
}
return vis[t];
}
ll dfs(int x,ll cur)
{
if(x==t) return cur;
ll f,flow=0;
for(int i=0;i<G[x].size();++i)
{
Edge e=edges[G[x][i]];
if(e.cap>0 && d[e.v]==d[x]+1)
{
f=dfs(e.v,min(cur,1ll*e.cap));
if(f) flow+=f,cur-=f,edges[G[x][i]].cap-=f,edges[G[x][i]^1].cap+=f;
}
if(!cur) break;
}
return flow;
}
ll maxflow()
{
ll flow=0;
for(;BFS();) flow+=dfs(s,inf);
return flow;
}
int main()
{
int i,j,k;
// setIO("input");
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) id[i][0]=++tot, id[i][1]=++tot;
for(i=1;i<=m;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c), add(a,b,c),add(b,a,c);
U[i]=a,V[i]=b,VAL[i]=c;
}
for(i=1;i<=n;++i) scanf("%d",&cc[i]);
S.dijkstra(1);
T.dijkstra(n);
addedge(id[1][0],id[1][1],inf);
addedge(id[n][0],id[n][1],inf);
for(i=2;i<n;++i)
{
addedge(id[i][0],id[i][1],cc[i]);
}
for(i=1;i<=m;++i)
{
int a=U[i],b=V[i];
if(S.d[a]+T.d[b]+VAL[i]==S.d[n])
{
addedge(id[a][1],id[b][0],inf);
}
swap(a,b);
if(S.d[a]+T.d[b]+VAL[i]==S.d[n])
{
addedge(id[a][1],id[b][0],inf);
}
}
s=id[1][0],t=id[n][1];
printf("%lld
",maxflow());
return 0;
}