Description
现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），网络中的路由器使用 1 到 n 编号，假设所有数据包一定沿最短路径转发，试计算从路由器 1 到路由器 n 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1 到路由器 n 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1 和 n 直接相连的链路。
本来以为是道水题，没想到是坑。
刚开始以为可以直接在原图上跑费用流。
但是有点权和最短路的限制，显然我们要重新建图。
在建图前跑SPFA求最短路（数据应该卡不掉，只要你常数小）。
由于只能在最短路上流，我们可以枚举每条边看是否在最短路上。
如果在就连边。
**注意：**这题的数据有重边，如果用邻接矩阵，要特判取min！！！！
如果你用vector就没事。
（这就是我爆零原因/kk）。
而对于c的限制，我们可以拆点，从i向i‘连一条ci的边。
但是1和n要连无限大。
最后就可以跑最大流惹qwq。
另：此题不用建源汇点，直接用1和n就行 虽然我还是建了。
很重要：
1.不开longlong见祖宗！
2.INF赋小见上帝！
3.不判重两行泪！
出题人好毒QAQ
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+9,INF=5e17;
int dis[N],ver[N<<1],w[N<<1],nxt[N<<1],h[N],cur[N],dep[N];
int n,m,c[N],x,y,z,ans,g[509][509],tot=1,s=0,t=1501;
bool vis[N];
inline void SPFA()
{
queue<int> Q;
for(int i=2;i<=n;i++) dis[i]=INF;
Q.push(1),vis[1]=true;dis[1]=0;
while(!Q.empty())
{
int u=Q.front();Q.pop();
vis[u]=0;
for(int i=0;i<=n;i++)
{
if(dis[i]>dis[u]+g[u][i]&&g[u][i]!=-1)
{
dis[i]=dis[u]+g[u][i];
if(!vis[i]) Q.push(i),vis[i]=true;
}
}
}
}
inline void addedge(int x,int y,int z)
{
ver[++tot]=y,w[tot]=z,nxt[tot]=h[x],h[x]=tot;
ver[++tot]=x,w[tot]=0,nxt[tot]=h[y],h[y]=tot;
}
inline bool bfs()
{
queue<int> Q;
memset(dep,-1,sizeof dep);
Q.push(s);dep[s]=0;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=h[u];i;i=nxt[i])
{
int v=ver[i];
if(dep[v]==-1&&w[i]>0)
{
Q.push(v);
dep[v]=dep[u]+1;
}
}
}
return dep[t]!=-1;
}
inline int dfs(int u,int flow)
{
if(u==t) return flow;
int delta,max_flow=0;
for(int i=cur[u];i;i=nxt[i])
{
cur[u]=i;
int v=ver[i];
if(dep[v]==dep[u]+1&&w[i]>0)
{
delta=dfs(v,min(w[i],flow));
flow-=delta;
max_flow+=delta;
w[i]-=delta;
w[i^1]+=delta;
if(!flow) break;
}
}
return max_flow;
}
inline void Dinic()
{
while(bfs())
{
memcpy(cur,h,sizeof h);
ans+=dfs(s,INF);
}
}
signed main()
{
// freopen("Alansp.out","w",stdout);
scanf("%lld%lld",&n,&m);
t=n*2+1;
memset(g,-1,sizeof g);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
if(g[x][y]==-1) g[x][y]=g[y][x]=z;
else g[x][y]=min(g[x][y],z),g[y][x]=g[x][y];
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++) if(g[i][j]!=-1) cout<<i<<' '<<j<<endl;
// }
for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
SPFA();
// for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
addedge(s,1,INF),addedge(n*2,t,INF);
for(int i=1;i<=n;i++)
{
if(i!=1&&i!=n) addedge(i,i+n,c[i]);
else addedge(i,i+n,INF);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(dis[i]+g[i][j]==dis[j]&&g[i][j]!=-1) addedge(i+n,j,INF);
}
}
Dinic();
printf("%lld",ans);
return 0;
}