XX星有許多城市，城市之間通過一種奇怪的高速公路SARS(Super Air Roam Structure---超級空中漫游結構）進行交流，每條SARS都對行駛在上面的Flycar限制了固定的Speed，同時XX星人對 Flycar的“舒適度”有特殊要求，即乘坐過程中最高速度與最低速度的差越小乘坐越舒服 ,(理解為SARS的限速要求，flycar必須瞬間提速/降速，痛苦呀 ),?
但XX星人對時間卻沒那么多要求。要你找出一條城市間的最舒適的路徑。(SARS是雙向的）。?

Input

輸入包括多個測試實例，每個實例包括：?
第一行有2個正整數n (1<n<=200)和m (m<=1000),表示有N個城市和M條SARS。?
接下來的行是三個正整數StartCity,EndCity,speed,表示從表面上看StartCity到EndCity,限速為speedSARS。speed<=1000000?
然后是一個正整數Q（Q<11),表示尋路的個數。?
接下來Q行每行有2個正整數Start,End, 表示尋路的起終點。

Output

每個尋路要求打印一行，僅輸出一個非負整數表示最佳路線的舒適度最高速與最低速的差。如果起點和終點不能到達，那么輸出-1。

Sample Input

4 4 1 2 2 2 3 4 1 4 1 3 4 2 2 1 3 1 2

Sample Output

1 0

主要運用了并查集，和貪心，先把所有公路的速度，由小到大排序，然后一條一條的取，最后所有公路差的最小值就是結果。

C++版本一

#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int INF=(0x7f7f7f7f7f); const int N=1000+10; int m,n,q,pre[N]; struct node{int f,t,l;node (){};node (int a ,int b ,int c){f=a;t=b;l=c;}bool operator <(const node &S)const{return l<S.l;}}e[N]; int find(int x){int r=x;while(pre[r]!=r)r=pre[r];return r; }int main() {while(scanf("%d%d",&n,&m)!=EOF){int a,b,c;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[i]=node(a,b,c);}scanf("%d",&q);sort(e+1,e+m+1);while(q--){int sp,ep;scanf("%d%d",&sp,&ep);int min1 = INF;for (int i=1; i<=m; i++) //枚舉{for (int j=1; j<=n; j++)pre[j] = j;for (int j=i; j<=m; j++){int fx = find(e[j].f);int fy = find(e[j].t);if (fx != fy)pre[fx] = fy;if (find(sp) == find(ep)){min1 = min(min1, e[j].l - e[i].l);break;}}}if (min1 == INF) puts("-1");else printf("%d\n", min1);}}//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的find the most comfortable road的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。