boj 164

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");
}