魔物消灭计划

第一行五个整数n,m,k,x,y.

第二行n个整数 $a_{i}$ , $a_{i} \in [0,k]$ ,表示第i个城市拥有某种类的宝石,特别的0表示该城镇没有任何一种宝石.

后面的m行,每行三个整数u,v,w,表示城市u和v之间有一条道路,清空这个道路上的魔物需要消耗的资源为w.

保证首都x和祭坛y不拥有任何一种宝石.

C++(clang++11) 解法, 执行用时: 47ms, 内存消耗: 24364K, 提交时间: 2021-02-07 23:27:36

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
const int N=1e2+5;
struct P{
	int u,w;
	bool operator<(const P&p)const{return w>p.w;}
}poi;
vector<P>p[maxn];
priority_queue<P>que;
int f[N][1050],a[N],n,k,x,y;
void Dij(int sta)
{
	while(!que.empty())
	{
		poi=que.top();que.pop();
		int u=poi.u;
		for(P pp:p[u])
			if(f[pp.u][sta]>f[u][sta]+pp.w){
				f[pp.u][sta]=f[u][sta]+pp.w;
				que.push({pp.u,f[pp.u][sta]}); 
			}
	}
}
int main()
{
	int m,u,v,w,nn;
	scanf("%d%d%d%d%d",&n,&m,&k,&x,&y);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	if(x!=y)a[y]=++k;++k;
	nn=k;
	for(int i=1;i<=n;i++)if(!a[i]&&i!=x&&i!=y)a[i]=nn++;
	mem(f,inf);
	for(int i=1;i<=n;i++)f[a[i]][(a[i]<k)?1<<a[i]:0]=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		p[a[u]].push_back({a[v],w});
		p[a[v]].push_back({a[u],w});
	}
	for(int sta=1,up=1<<k;sta<up;sta++)
	{
		for(int i=0;i<nn;i++)
		{
			for(int s=sta&(sta-1);s;s=sta&(s-1))
				f[i][sta]=min(f[i][sta],f[i][sta^s]+f[i][s]);
			if(f[i][sta]!=inf)que.push({i,f[i][sta]});
		}
		Dij(sta);
	}
	printf("%d\n",f[0][(1<<k)-1]);
}

详情