通行证

　

金山通行证

通行证

题目大意

某俄罗斯贵族要在车上用闪光灯。

每条道路由若干个机构管辖，要在这条街道上使用闪光灯，至少要拥有其中一个机构的通行证。

找出一种方案，使得能通行与家与工作地点之间，且需要的通行证数最少。能，则输出要的通行证数和每个通行证的编号；否则，输出“impossible”

（家的编号为0，工作地点的编号为1）

输入样例

3 3 3
0 2 0
0 2 1
1 2 2

输出样例

2
0 2

数据范围

2 <= n <= 30

1 <= k <= 20

思路

这道题要用到dfs。

其实就是用dfs一波，同时要记得标记路程，就可以了。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
struct note
{
	int l,j;
}g[31][31];
int k,n,m,a,b,c,number[31],answer[31],ans=2147483647;
bool in[31],f[31];
void dfs(int now,int an)//dfs
{
	if (an>=ans) return ;//距离已超过最小值，绝对不是最短
	if (now==1)//到达
	{
		if (an<ans)//路径更短
		{
			ans=0;
			for (int i=0;i<=k-1;i++)
			if (f[i])
			answer[++ans]=i;//标记
		}
		return ;
	}
	in[now]=1;//标记
	for (int i=1;i<=number[now];i++)
	if (!in[g[now][i].l])//判断是否到过
	if (f[g[now][i].j]) dfs(g[now][i].l,an);//dfs（通行证已有）
	else//还没有通行证
	{
		f[g[now][i].j]=1;//标记
		dfs(g[now][i].l,an+1);//dfs
		f[g[now][i].j]=0;//回溯
	}
	in[now]=0;//回溯
}
bool cmp(note x,note y)
{
	return x.j<y.j;
}
int main()
{
//	freopen("license.in","r",stdin);
//	freopen("license.out","w",stdout);
	scanf("%d%d%d",&k,&n,&m);//读入
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);//读入
		g[a][++number[a]].l=b;//标记
		g[a][number[a]].j=c;
		g[b][++number[b]].l=a;
		g[b][number[b]].j=c;
	}
	for (int i=0;i<=n-1;i++)
	sort(g[i]+1,g[i]+number[i]+1,cmp);//排序
	dfs(0,0);//dfs
	if (ans!=2147483647)//判断是否能到达
	{
		printf("%d\n",ans);//输出
		for (int i=1;i<=ans;i++)
		printf("%d ",answer[i]);//输出
	}
	else printf("Impossible");//不能到达
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

文章最后发布于: 2019-07-07 14:22:06

相关阅读

在校大学生如何办理护照及港澳通行证？

注：办理护照和港澳通行证整体流程差不多，差别在于：可以凭在校证明异地办理护照（户口不在办理点），但是需要开具本地居住证明才能异地办理

淘宝实人通行证是什么？与实人认证有什么区别？

随着淘宝网上购物越来越普遍和快捷，我们泄露的私人信息也越来越多，所以保障个人信息安全就越来越重要了，所以阿里和腾讯推出了实人通

淘宝实人通行证好吗?实人认证是怎么回事?

很多买家朋友都想要知道淘宝实人通行证是干什么的，到底有什么好处?所以今天就让小编给大家做一些说明一下相关的内容，希望大家通过

帐号通行证体系设计

2013年7月发布的《第32次互联网络发展状况统计报告》显示，截至2013年6月底，我国网民规模已达到5.91亿。其中手机网民达4.64亿，域名总

金山通行证是什么，金山通行证网络账号怎么注册！

摘要：现在的手机杀毒软件是种类较多，很多人在疑惑为什么会有如此多的安全软件开始着手手机安全领域，对于手机的安全来说，选择一款好的