思路:先按照速度大小对边排序,再枚举最终路径中的速度最大值,并查集,更新答案
#include<iostream> #include<vector> #include<algorithm> using namespace std; +; struct BCJ{ int fa[maxn],n; void init(int n){ this->n=n; ;i<=n;i++) fa[i]=i; } int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } bool Judge(int a,int b){ return find(a)==find(b); } void Union(int a,int b){ if(find(a)!=find(b)){ fa[find(a)]=find(b); } } }; struct Edge{ int from,to,dist; bool operator<(const Edge& b)const{ return dist<b.dist; } }; int gcd(int a,int b){ ?a:gcd(b,a%b); } BCJ bcj; vector<Edge> e; ,b=-; int main() { int f,t,d; cin>>N>>M; ;i<M;i++){ cin>>f>>t>>d; e.push_back((Edge){f,t,d}); } cin>>S>>T; sort(e.begin(),e.end()); ;i<e.size();i++) { bcj.init(N); ;j--){ if(!bcj.Judge(e[j].from,e[j].to)){ bcj.Union(e[j].from,e[j].to); if(bcj.Judge(S,T)){ &&b==-) a=e[i].dist,b=e[j].dist; else if(a*e[j].dist>b*e[i].dist) a=e[i].dist,b=e[j].dist; break; } } } } &&b==-) cout<<"IMPOSSIBLE"; else{ cout<<a/gcd(a,b); ) cout<<'/'<<b/gcd(a,b); } ; }