Description
古老的原始部落ACElite的居民们一直过着日出而做,日落而出的简单生活。酋长dalong为了改善大家的生活,研究出了一种新的无线通讯工具,便于大家之间相互交流。这需要架设多个基站进行通信。但由于各种原因,他无法保证这项技术是否成功,所以决定和champ测试一下。
现在我们知道ACElite部落有n(n<=10000)个山头,每个山头都可以架设基站。但如果山头间的距离大于c,基站间便无法通信。
在测试时dalong在s山头,champ在t山头,他们需要架设一些基站以进行通信。于是dalong希望YesXdogdog购买一些材料来架设基站,为了节约资源,YesXdogdog希望如果dalong和champ能通信的情况下架设的基站尽可能的少。当然,如果不能通信,他也没办法了。你能帮助YesXdogdog解决这个问题吗?
Input
单组数据测试
输入的第一行为3个数,n,m,c。表示ACElite部落有n(n<=10000)个山头,m(m<=100000)表示有m条边,c表示两个基站通信的最大距离。
后面有m行,每行3个数a,b,l,表示a,b(1<=a,b<=n)山头之间可以架设基站且它们的距离为l。
最后一行为两个数 s,t表示dalong和champ的位置
Output
一个数,最少需要架设的基站。
如果无法通信,输出Impossible
Sample Input
4 4 10
1 2 3
2 3 9
1 4 8
1 3 11
1 3
Sample Output
3
Hint
巨大的输入输出,推荐printf,scanf
思路:
bfs求两点最短路径
代码:
#include<iostream> #include<vector> #include<queue> using namespace std; #define N 10005 vector<int>Graph[N]; bool visit[N]; struct node{ int v; int f; }; bool bfs(int s,int t,int &cnt) { bool flag = false; node tmp; tmp.v = s; tmp.f = 1; queue<node>q; q.push(tmp); while(q.size()) { tmp = q.front(); visit[tmp.v] = true; q.pop(); if(tmp.v==t) { cnt = tmp.f; flag = true; break; } int num = Graph[tmp.v].size(); for(int i=0;i<num;i++) { int next = Graph[tmp.v][i]; if(visit[next]==false) { node temp; temp.v = next; temp.f = tmp.f+1; q.push(temp); } } } return flag; } int main() { int n,m,c; scanf("%d %d %d",&n,&m,&c); memset(visit,0,sizeof(visit)); for(int i=0;i<m;i++) { int a,b,l; scanf("%d %d %d",&a,&b,&l); if(l<=c) { Graph[a].push_back(b); Graph[b].push_back(a); } } int s,t,cnt = 0;; scanf("%d %d",&s,&t); if(bfs(s,t,cnt)) printf("%d\n",cnt); else printf("Impossible\n"); }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
JAVA_BOJ
boj:算法
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
BOJ:日本央行
boj:算法求解