1001 舒适的路线

--write by zhuwx 2019-06-24 20:57:47 +0800 CST

点击量:26

Z小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点(编号为1,2,3,…,N),这些景点被M(0<M≤5000)条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。也许是为了保护该地的旅游资源,Z小镇有个奇怪的规定,就是对于一条给定的公路Ri,任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服,因此大家从一个景点前往另一个景点的时候,都希望选择行使过程中最大速度和最小速度的比尽可能小的路线,也就是所谓最舒适的路线。输入描述 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<N≤500)

M(0<M≤5000)

Vi在int范围内

#include <bits/stdc++.h>
using namespace std;
vector<int>edges[505];
vector<int>d[505][505]; 
bool vis[505]={0};
struct node{
	int ma,mi,id;
	node(int ma,int mi,int id):ma(ma),mi(mi),id(id){}
};
struct ans{
	int a,b;
	ans(int a,int b):a(a),b(b){}
	bool operator<(const ans&rhs)const{return (double)a/b<(double)rhs.a/rhs.b;}
};
vector<ans>Ans;
int main(){
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		if(d[a][b].empty()){
			edges[a].push_back(b);
			edges[b].push_back(a);
		}
		d[a][b].push_back(c);
		d[b][a].push_back(c);
	}
	int b,e;
	vis[b]=1;
	cin>>b>>e;
	queue<node>q;
	q.push(node(-1,0x7fffffff,b));
	int count=10000;
	while(!q.empty()&&count--){
		node t(q.front());q.pop();
		if(t.id==e){
			Ans.push_back(ans(t.ma,t.mi));
			continue;
		}
		for(int i=0;i<edges[t.id].size();i++)/*if(!vis[edges[t.id][i]])*/for(int j=0;j<d[t.id][edges[t.id][i]].size();j++){
			q.push(node(max(t.ma,d[t.id][edges[t.id][i]][j]),min(t.mi,d[t.id][edges[t.id][i]][j]),edges[t.id][i]));
			//vis[edges[t.id][i]]=1;
		}
	}
	if(Ans.empty())return cout<<'IMPOSSIBLE
',0;
	sort(Ans.begin(),Ans.end());
	ans t(Ans.front());
	if(t.a%t.b==0)cout<<t.a/t.b<<endl;
	else cout<<t.a/__gcd(t.a,t.b)<<'/'<<t.b/__gcd(t.a,t.b)<<endl;
	return 0;
}