给你一个图,每个点可以被经过\(a_i\)次,求有多少个人可以走最短路到n点
\(n \le 500\)
极其水的一道题,就当做复习最短路板子了
先跑最短路,然后把满足\(dis[v]=dis[u]+t[i].w\)的点连起来,拆个点就完事了
#include #include #include #include #include #include #include #include #include #include #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(xy) 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 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 > 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