题解：P1078 [NOIP 2012 普及组] 文化之旅

大部分人喜欢用 DFS,这里分享一种极少人用的写法（毕竟有点麻烦）。不知道这种写法会不会也是不完全正确的。

简化题意：

每个国家都有一种文化。某人要从 S 国出发前往 T 国，它到每一个国家就会学习这个国家的文化，它不想重复到相同文化的国家。有的国家不允许会某些文化的外来人到访。给出无向图，求从 S 国到 T 国至少要走多少路（无解输出 -1）。

题目思路：

很明显，题目涉及最短路问题，且

1≤m≤n^2

，所以属于稠密图，应该优先选择 dijkstra 算法。

难点是：这题需要记录每一个文化是否曾经学过。

考虑到国家数量和文化数量都比较少（只有 100），即使四次方也不会炸。所以我们可以考虑在 dijkstra 优先队列的

node

类型中加入一个布尔型的

vis

数组，记录每个国家是否曾经到过。然后在 dijkstra 函数中选择下一批国家入队时检查，检查是否有

vis

为

true

的文化被该国文化排斥或已学习该国文化。

注意：优先队列类型中包含整个数组，我们要尽量避免赋值（因为赋值也是要占用时间的），可以使用原变量更改，然后用这个变量判断，最后再改回来。

AC代码如下：

CPP

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct nod1
{
	int to,w;
};
const int NR=101;
struct nod2
{
	int x,d;
	bool vis[NR];
	bool operator <(const nod2 &B) const
	{
		return d>B.d;
	}
};
vector<nod1> g[NR];
int k,c[NR],dis[NR];
bool a[NR][NR];
bool chck(int v,bool vis[]) //判断文化v是否排斥vis数组中为true的文化
{
	int i;
	for(i=1;i<=k;i++)
		if(vis[i] && a[v][i]) return false;
	return true;
}
void dijk(int s)
{
	priority_queue<nod2> q;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	nod2 tmp;
	tmp.x=s;
	tmp.d=0;
	memset(tmp.vis,false,sizeof(tmp.vis));
	tmp.vis[c[s]]=true;
	q.push(tmp);
	while(!q.empty())
	{
		if(q.top().d>dis[q.top().x]) //防止进入第35行O(100)的赋值语句
		{
			q.pop();
			continue;
		}
		nod2 x=q.top();
		q.pop();
		int i;
		for(i=0;i<g[x.x].size();i++)
			if(dis[x.x]+g[x.x][i].w<dis[g[x.x][i].to] && !x.vis[c[g[x.x][i].to]] && chck(c[g[x.x][i].to],x.vis)) //根据题目要求要判断是否学过、是否排斥
			{ //节省赋值时间，所以先在原nod2中修改，放入队列，再将nod2中的值改回原样
				dis[g[x.x][i].to]=dis[x.x]+g[x.x][i].w;
				x.vis[c[g[x.x][i].to]]=true;
				int t=x.x;
				x.x=g[x.x][i].to;
				q.push(x);
				x.x=t;
				x.vis[c[g[x.x][i].to]]=false;
			}
	}
	return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
	int n,m,s,t,i,j;
	cin>>n>>k>>m>>s>>t;
	for(i=1;i<=n;i++) cin>>c[i];
	for(i=1;i<=k;i++)
		for(j=1;j<=k;j++) cin>>a[i][j];
	while(m--)
	{
		int u,v,d;
		cin>>u>>v>>d;
		g[u].push_back({v,d});
		g[v].push_back({u,d});
	}
	dijk(s);
	if(dis[t]>1e9) cout<<-1;
	else cout<<dis[t];
	return 0;
}

注意事项：

1、需要注意放入

chck

函数的是文化，不是国家。

2、一定要记得改回因避免赋值而被更改过的

node

类型变量，而且一定要改齐。

题解：P1078 [NOIP 2012 普及组] 文化之旅

文章操作

简化题意：

题目思路：

注意事项：

相关推荐

评论

题解：P1078 [NOIP 2012 普及组] 文化之旅