codevs1001 舒适的路线 贪心枚举+并查集

2017年03月18日 8点热度 0人点赞 0条评论
题目描述 Description

Z小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1

输入描述 Input Description

第一行包含两个正整数,N和M。
接下来的M行每行包含三个正整数:x,y和v(1≤x,y≤N,0 最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

输出描述 Output Description

如果景点s到景点t没有路径,输出“IMPOSSIBLE”。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。

样例输入 Sample Input

样例1
4 2
1 2 1
3 4 2
1 4

样例2
3 3
1 2 10
1 2 5
2 3 8
1 3

样例3
3 2
1 2 2
2 3 4
1 3

样例输出 Sample Output

样例1
IMPOSSIBLE

样例2
5/4

样例3
2

数据范围及提示 Data Size & Hint

N(1

M(0

Vi在int范围内

//巧妙的贪心枚举,贪心地找部分边构成的连通图 
#include
#include
#define ll long long
#define INF 99999999
using namespace std;
struct node{
	int x,y,w;
	friend inline bool operator<(node a,node b){
		return a.w>n>>m;
	for(int i=0;i>a[i].x>>a[i].y>>a[i].w;
	cin>>s>>t;
	sort(a,a+m);
	for(int i=0;i=0;j--){
			int fx=find(a[j].x),fy=find(a[j].y);
			f[fx]=fy;
			if(find(s)==find(t)){
				if(cmp(a[i].w,a[j].w,a1,a2))
				a1=a[i].w,a2=a[j].w;
				break;
			}
	}
	}
	if(a1==INF)
	cout<<"IMPOSSIBLE"<
未经允许不得转载!codevs1001 舒适的路线 贪心枚举+并查集

update

纸上得来终觉浅, 绝知此事须躬行。