Description:

给你一个图,每个点可以被经过\(a_i\)次,求有多少个人可以走最短路到n点

Hint:

\(n \le 500\)

Solution:

极其水的一道题,就当做复习最短路板子了

先跑最短路,然后把满足\(dis[v]=dis[u]+t[i].w\)的点连起来,拆个点就完事了

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const ll mxn=2e5+5,inf=1e18;

ll S,T,n,m,k,cnt,cnt1,ans,dis[mxn],vis[mxn],hd1[mxn],a[mxn],dep[mxn],cur[mxn],mp[500][500],hd[mxn];

ll dx[9]={1,1,-1,-1,3,3,-3,-3};

ll dy[9]={3,-3,3,-3,1,-1,1,-1};

inline ll read() {

    char c=getchar(); ll x=0,f=1;

    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

    return x*f;

}

inline void chkmax(ll &x,ll y) {if(x<y) x=y;}

inline void chkmin(ll &x,ll y) {if(x>y) x=y;}

struct ed {

    ll to,nxt,w;

}t[mxn<<1],t1[mxn<<1];

void add1(ll u,ll v,ll w) {

	t1[++cnt1]=(ed) {v,hd1[u],w}; hd1[u]=cnt1;

}

inline void add(ll u,ll v,ll w) {

    t[cnt]=(ed) {v,hd[u],w}; hd[u]=cnt++;

    t[cnt]=(ed) {u,hd[v],0}; hd[v]=cnt++;

}

ll bfs() {

    memset(dep,0,sizeof(dep)); queue<ll > q;

    q.push(S); dep[S]=1;

    for(ll i=0;i<=n*2+1;++i) cur[i]=hd[i];

    while(!q.empty()) {

        ll u=q.front(); q.pop();

        for(ll i=hd[u];i!=-1;i=t[i].nxt) {

            ll v=t[i].to;

            if(dep[v]==0&&t[i].w>0)

                dep[v]=dep[u]+1,q.push(v);

        }

    }

    if(dep[T]==0) return 0;

    return 1;

}

ll dfs(ll u,ll f) {

    if(u==T) return f;

    for(ll &i=cur[u];i!=-1;i=t[i].nxt) {

        ll v=t[i].to;

        if(dep[v]==dep[u]+1&&t[i].w>0) {

            ll tp=dfs(v,min(f,t[i].w));

            if(tp>0) {

                t[i].w-=tp;

                t[i^1].w+=tp;

                return tp;

            }

        }

    }

    return 0;

}

void Dinic() {

    while(bfs())

        while(ll tp=dfs(S,inf))

            {ans+=tp;}

}

ll get(ll x,ll y) {

	return (x-1)*m+y;

}

priority_queue<pair<ll ,ll > > q;

void Dij() {

	q.push(make_pair(0,1)); memset(dis,0x3f,sizeof(dis));

	dis[1]=0;

	while(!q.empty()) {

		ll u=q.top().second; q.pop();

		if(vis[u]) continue ;

		for(ll i=hd1[u];i;i=t1[i].nxt) {

			ll v=t1[i].to;

			if(vis[v]) continue ;

			if(dis[v]>dis[u]+t1[i].w) {

				dis[v]=dis[u]+t1[i].w;

				q.push(make_pair(-dis[v],v));

			}

		}

	}

}

void init() {

	for(ll i=1;i<=n;++i) {

		for(ll j=hd1[i];j;j=t1[j].nxt) {

			ll v=t1[j].to;

			if(dis[v]==dis[i]+t1[j].w) add(i+n,v,inf);

		}

	}

}

int main()

{

	memset(hd,-1,sizeof(hd)); ll u,v,w;

	n=read(); m=read(); T=2*n+1; add(S,1,inf); add(1,n+1,inf); add(n,n+n,inf);  add(n+n,T,inf);

	for(ll i=1;i<=m;++i) {

		u=read(); v=read(); w=read();

		add1(u,v,w); add1(v,u,w);

	}

	a[1]=read();

	for(ll i=2;i<n;++i) a[i]=read(),add(i,i+n,a[i]);

	a[n]=read();

	Dij(); init(); Dinic();

	printf("%lld",ans);

	return 0;

}