codevs 1001 舒适的路线
1.看到题目，要找某种最优条件，又是二维图，用搜索，然后这个应该是DFS，并且判断是否能到达也不是问题。但新的一个问题是，2个点之间可能存在多条边，这个我思前想后也不知道该如何进行存储这个数据。
2.突然感觉这好像是个非常神难的题，看题解吧。
3.看了题解才发现，原来思维还是挺简单的，下面转载一份题解：
4.以前被这个题吓到了。。。以为是个神题。。。木有想到数据范围支持 暴力+并查集。。。
把边 按照权值(也就是题目中 能在边上行驶的最大速度v) 升序排列
然后从左到右扫一遍所有的边
比如现在扫到了一条边x（这时并查集要赋值成原始值）
就把x作为要选的 权值最小边，然后往这条边的右边扫，并且用并查集不断维护连通性
这里相当于就是只能选比 边x 权值大的边直到找到一条边y，且y满足 加上这条边y 使起点和终点 能联通那么边y就是 使得起点和终点相通的边集中 最大边相当于枚举分母，并求出该分母对应的最小分子 然后对所有求得的分数取最小值的过程。。。
这样扫一遍，取min就好了。。。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 5009using namespace std;int n,m,la,fa[N],maxx,minn,ans2,ans1,beg,end;struct node{ int fr,to,len;}a[N];void addedge(int x,int y,int z){ a[++la].fr=x,a[la].to=y,a[la].len=z;}int cmp(node a,node b){ return a.len<b.len;}int find(int x){ if (x==fa[x]) return x; fa[x]=find(fa[x]); return fa[x];}int gcd(int x,int y){ if (y==0)return x;else return gcd(y,x%y);}int main(){ int i,j,k,x,y,z; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } cin>>beg>>end; sort(a+1,a+m+1,cmp); for (i=1;i<=m;i++) { for (j=1;j<=n;j++) fa[j]=j; maxx=0; minn=2*1e9; for (j=i;j<=m;j++) // 只考虑更长的边 { if (find( a[j].fr )!=find( a[j].to )) { fa[ find( a[j].fr ) ]=find( a[j].to ); maxx=max(maxx,a[j].len); minn=min(minn,a[j].len); if (find(beg)==find(end)) break; } } if (find(beg)==find(end)) //联通的 if(!ans1 && !ans2 || maxx*ans2 < ans1*minn) //大小比例更小 ans1=maxx,ans2=minn; } // ans1为 最大速度，ans2为最小速度 if (!ans1&&!ans2) cout<<"IMPOSSIBLE"<<endl; else if (ans1%ans2==0) cout<<ans1/ans2<<endl; else cout<<ans1/gcd( ans1,ans2 )<<"/"<<ans2/gcd(ans1,ans2);}```转载至：http://codevs.cn/wiki/solution/?PRoblem_id=1001
5.现在想来，看起来很难的题目也许思路是很简单的，不要轻易地被表面迷惑了。可能有其他的解决途径，而且还要多发散思维，不畏挫折。
新闻热点
疑难解答
