自动搬运

查看原文

来自洛谷，原作者为

	Mr_Az 我的尸体不会腐烂在泥土里，我会像鸟儿一样死在天空中。

搬运于2025-08-24 23:06:28，当前版本为作者最后更新于2025-05-15 21:16:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P11327 [NOISG 2022 Finals] Voting Cities

Algorithm:

分层图最短路。

Solution:

看到 $5$ 张优惠券就笑了，分层最短路的感觉又回来了。

按照使用了多少张优惠券进行分层，记状态 $o$ 的第 $i$ 位二进制位为第 $i$ 张优惠券的使用情况，跑一边分层图最短路求最小值即可。

分层图最短路是指题目中有 $k$ 种操作可以使通过一条路径的代价减少，但是会带来一定的代价，求最后的最短路。对于此，考虑类似 DP 的思想，记 $dis_{i,j}$ 为从起点到第 $i$ 个节点，花费的操作状态为 $j$（有些题目可以不用记录状态，记录使用了几次操作）。转移可以写作：

$$dis_{v,\operatorname{op}(j)}=\min(\min_{u \to v}dis_{u,j}+w,dis_{u,\operatorname{op}(j)}+\operatorname{op}(w)) $$

其中代表此次操作对状态与边权的改变，$w$ 为这条边的边权。跑一边最短路计算即可。

Code:

namespace Mr_Az{
	const int M=5008,N=M*35;
	int T=1;
	int n,m,q,k;
	int a[N],p[10],dis[N];
	bool vis[N];
	vector<pii> e[N];
	inline int id(int x,int y){return x*n+y;}
	inline void dij(){
		mem(dis,inf);mem(vis,0);
		priority_queue<pii> q;
		while(q.size()) q.pop();
		for(rint i=1;i<=k;i++) q.push({0,id(0,a[i])}),dis[id(0,a[i])]=0;
		while(q.size()){
			auto [azzzz,u]=q.top();q.pop();
			if(vis[u]) continue;
			vis[u]=1;
			for(auto [v,w]:e[u]){
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					q.push({-dis[v],v});
				}
			}
		}
		return ;
	}
	inline void solve(){
		read(n,m,k);
		for(rint i=1;i<=k;i++) read(a[i]),a[i]++;
		for(rint i=1,u,v,w;i<=m;i++){
			read(u,v,w);u++;v++;swap(u,v);
			for(rint s=0;s<(1<<5);s++){
				e[id(s,u)].eb(id(s,v),w);
				for(rint j=0;j<5;j++){
					if(((s>>j)&1)==0){
						e[id(s,u)].eb(id(s+(1<<j),v),w/10*(9-j));
					}
				}
			}
		}
		dij();
		read(q);
		while(q--){
			int st,ans=-1,res=0;
			read(st);for(rint i=0;i<5;i++) read(p[i]);
			st++;
			for(rint s=0;s<(1<<5);s++){
				res=dis[id(s,st)];
				if(res==dis[0]) goto nxt;
				for(rint i=0;i<5;i++){
					if((s>>i)&1){
						if(p[i]==-1) goto nxt;
						res+=p[i];
					}
				}
				if(ans==-1) ans=res;
				else ans=min(ans,res);
				nxt:;
			}
			printf("%lld\n",ans);
		}
	}
	inline void mian(){if(!T) read(T);while(T--) solve();}
}