网站开发外包公司坑,孝感企业做网站,海外网站加速免费,湖南3合1网站建设价格通行证
jzoj 2013
题目大意#xff1a;
有一个图#xff0c;走某一条路需要某个通行证#xff08;数据给出所有可选择的#xff09;#xff0c;现在要从某个点到另一个点#xff0c;问最少要多少个通行证
样例输入
3 3 3
0 2 0
0 2 1
1 2 2样例输出
2
0 2数据范围限…通行证
jzoj 2013
题目大意
有一个图走某一条路需要某个通行证数据给出所有可选择的现在要从某个点到另一个点问最少要多少个通行证
样例输入
3 3 3
0 2 0
0 2 1
1 2 2样例输出
2
0 2数据范围限制
2 n 30 1 k 20。
解题思路
直接走每一条路然后要通行证的就记录下来最后看看那一条路用到的通行证最少
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int k,n,m,x,y,z,tot,ans,s[50],p[50],pp[50],num[50];
struct rec
{int to,t;
}a[50][50];
void dfs(int dep,int now)
{if (nowans) return;if (dep1)//到了{if (nowans)//更优{ans0;for (int i0;ik;i)if (p[i])//要用的s[ans]i;}return;}pp[dep]1;for (int i1;inum[dep];i)if (!pp[a[dep][i].to])//没有重复到一个点if (p[a[dep][i].t]) dfs(a[dep][i].to,now);//这个通行证已经有了else{p[a[dep][i].t]1;//记录dfs(a[dep][i].to,now1);//dfsp[a[dep][i].t]0;//清零}pp[dep]0;
}
bool cmp(rec xx,rec yy){return xx.tyy.t;}
int main()
{scanf(%d %d %d,k,n,m);for (int i1;im;i){scanf(%d %d %d,x,y,z);a[x][num[x]].toy;//记录到达的点a[x][num[x]].tz;//记录通行证编号a[y][num[y]].tox;a[y][num[y]].tz;}for (int i0;in;i)sort(a[i]1,a[i]1num[i],cmp);//排序保证字典序ans2147483647;dfs(0,0);if (ans50){printf(%d\n,ans);for (int i1;ians;i)printf(%d ,s[i]);//输出}else printf(Impossible);return 0;
}
