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.現在想來，看起來很難的題目也許思路是很簡單的，不要輕易地被表面迷惑了?？赡苡衅渌慕鉀Q途徑，而且還要多發散思維，不畏挫折。
新聞熱點
疑難解答
