HDU 3873 Invade the Mars(灵活的dijstra魔改)

灵活的dijstra魔改)"/>

HDU 3873 Invade the Mars(灵活的dijstra魔改)

传送门

给定一张图,求 1 1 1到 n n n的最短路

进入到第 i i i城市当且仅当所有 i i i的子城市都被进入

而且由于从 1 1 1出发的是一个军队,所以占领城市可以同时进行

非常灵活的一题…对于 d i j s t r a dijstra dijstra的魔改

因为每个点是有限制的,不能马上入队,只有当不受任何城市保护了才能入队更新别人

记录一下每个点还受多少点保护 i n [ i ] in[i] in[i],以及每个点保护了哪些点

那么每次从优先队列拿出一个不受保护的点 u u u

所有受到点 u u u保护的点的 i n [ i ] − − in[i]-- in[i]−−

且执行 d i s [ v ] = m a x ( d i s [ v ] , d i s [ u ] ) dis[v]=max(dis[v],dis[u]) dis[v]=max(dis[v],dis[u])

因为点 v v v至少等到所有保护自己的城市攻占后才能来到城市 v v v

若发现 i n [ v ] = = 0 in[v]==0 in[v]==0就可以开始入队更新别人

然后按照 d i j s t r a dijstra dijstra的原始操作来即可,只有当 i n [ i ] = = 0 in[i]==0 in[i]==0才入队

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
const int maxn = 2e6+10;
struct edge{int to,nxt,w;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int w)
{d[++cnt] = (edge){v,head[u],w},head[u] = cnt;
}
int dis[maxn],ci[maxn],n,m,T,vis[maxn];
vector<int>vec[maxn];
typedef pair<int,int>p;
priority_queue<p,vector<p>,greater<p> >q;//优先队列 
void dijstra()
{for(int i=1;i<=n;i++)	dis[i] = inf,vis[i] = 0;dis[1] = 0, q.push( p(0,1) );while( !q.empty() ){int u = q.top().second; q.pop();if( vis[u] )	continue;vis[u] = 1;for(int i=0;i<vec[u].size();i++)//开始解放所有的{int v = vec[u][i];dis[v] = max( dis[v],dis[u] );if( --ci[v]==0 )		q.push( p(dis[v],v) );} for(int i=head[u];i;i=d[i].nxt ){int v = d[i].to;if( dis[v] > dis[u]+d[i].w ){dis[v] = dis[u]+d[i].w;if( ci[v]==0 )	q.push( p(dis[v],v) );	}}}
}
signed main()
{cin >> T;while( T-- ){cin >> n >> m;for(int i=1;i<=m;i++){int l,r,w; scanf("%lld%lld%lld",&l,&r,&w);add(l,r,w);}for(int i=1;i<=n;i++){int k; scanf("%lld",&k);ci[i] = k;//还有k个节点没有while( k-- ){int x; scanf("%lld",&x);vec[x].push_back( i );//解放x之后,所以相关节点都减1 } }dijstra();printf("%lld\n",dis[n]);cnt = 1;for(int i=1;i<=n;i++)head[i] = ci[i] = 0, vec[i].clear();}
}