自动搬运

查看原文

来自洛谷，原作者为

	小塘空明 **

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

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

以下是正文

先%下楼上的分层图2333

观察数据，发现p<=13,n<=200，所有我们很明显可以将状态保存下来。

设d[i][j]表示当前到达i，状态为j所需要的最短时间。

根据dijkstra的性质，n第一次被取出时就是答案。

在实际运算中，我们保存一个三元组(t,x,s);

t为当前的值，x为当前的点，s为走到当前的点所能铸的剑的状态，将s或上当前点铁匠能铸的剑的值，进行合法的转移即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=2e2+10,M=3e3+10,inf=1e9;
int n,m,k,p,tot,a[N],d[N][N*50],vis[N][N*50];
int head[N],next[M*2],ver[M*2],edge[M*2],cost[M*2];
priority_queue<pair<pair<int,int>,int> >q;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y,int z,int c){
	ver[++tot]=y;edge[tot]=z;cost[tot]=c;next[tot]=head[x];head[x]=tot;
}
inline int dijkstra(){
	for(int i=1;i<=n;i++){
		for(int j=0;j<(1<<p);j++) d[i][j]=inf;
	}
	d[1][0]=0;q.push(make_pair(make_pair(0,1),0));
	while(q.size()){
		int t=-q.top().first.first,x=q.top().first.second,s=q.top().second;q.pop();
		if(x==n) return t; 
		if(vis[x][s]) continue;
		vis[x][s]=1;s|=a[x];
		for(int i=head[x];i;i=next[i]){
			int y=ver[i],z=edge[i],c=cost[i];
			if((s|c)!=s) continue;
			if(d[y][s]>t+edge[i]){
				d[y][s]=t+edge[i];
				q.push(make_pair(make_pair(-d[y][s],y),s));
			}
		}
	}
	return -1;
}
int main(){
	n=read();m=read();p=read();k=read();
	for(int i=1;i<=k;i++){
		int w=read(),q=read();
		for(int j=1;j<=q;j++){
			int x=read();a[w]|=1<<(x-1);
		}
	}
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read(),s=read(),c=0;
		for(int j=1;j<=s;j++){
			int v=read();c|=1<<(v-1);
		}
		add(x,y,z,c);add(y,x,z,c);
	}
	printf("%d\n",dijkstra());
	return 0;
}