【最短路】Flycar

版权声明：本篇随笔版权归作者Etta（http://www.cnblogs.com/Etta/）所有，转载请保留原地址!

一．问题描述

Hecy被FC星人劫持了！

“长的帅也是一种罪过吗？”，Hecy问劫持他的生物，结果被暴打。唉，原来Hecy被劫持的原因是FC星人看中了他的编程才能（“我真的长的不帅吗？”Hecy不死心地问另一个生物，结果再次被暴打）。

FC星有许多城市，某些城市之间无法直接到达，但某些城市之间可以通过一种奇怪的高速公路SARS（Super Air Roam Structure 超级空中漫游结构）进行人员或物资的交流运输。在SARS上有且仅有一种“车”可以行驶，那就是传说中的极品飞车Flycar。东东们就是乘坐着Flycar在SARS上运动的。与地球相似地，每条SARS都对行驶在他上面的Flycars有限速要求——不同的是这既不是限最高速，也不是限最低速，而是限固定速，也就是说Flycars必须以所限速度行驶，否则就要被TS（Traffic System）来一次ts（tiger strike虎击）——这可不是好玩的！

同时FC星人对flycar的“舒适度”也有特殊的要求。他们认为乘坐一次flycar过程中，flycar达到的最高速与最低速之间的差越小，本次乘坐越舒适（可以理解，因为SARS的限速要求，flycar都必须瞬间提/降速，痛苦啊）——FC星人对时间却没那么多要求。

因此Hecy的任务就明确了：为FC星上几乎垄断了flycar市场的全星通用汽车公司（CC）设计新一代自动寻路flycar，使得该flycar能自动寻找两城市间最舒适的到达路径。

任务对于给定的公路网以及两个城市s、t，求出从s到t的最舒适路径。

输入输出格式

输入格式：

输入输入数据的第一行两个正整数n、m（1<=n〈=200，1〈=m<=1000），n、m分别表示城市数和公路数。

接下来的m行每行三个正整数i、j、num（num〈=1000000），表示城市I,j之间有一条道路，该路的限速为num.

接下来输入整数t，表示t组询问。

每组询问给出两个正整数s、t,表示初始城市和目标城市。

输出格式：

输出每组询问输出最舒适值。

输入输出样例

输入样例#1

2 1

1 2 1

1 2

输出样例#1

二．问题分析

看到这道题就去codevs刷1001舒适的路线了……

利用并查集，有顺序地循环枚举最大最小路径，求出答案即可。

三．解决问题

1.给边从小到大排序

2.for(i:1~m)+for(j:i~m)遍历每一条边，若边两端点不再同一集合内则合并两点，若合并后st与en在同一集合内，更新答案并break

Tip：其实题目不完整，无法到达是要输出-1的(⊙o⊙)…

四.代码实现

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int A=205,B=1005,inf=5e8;
 6 
 7 int n,m,sum,minn,maxn=inf,st,en;
 8 int i,j,x,y,z,k,s,t,ans1=inf,ans2=0;
 9 bool bo;
10 int fa[A],ex[A],ans[A];
11 struct  edge{
12     int from,to,len;
13 }e[B];
14 
15 void build(int x,int y,int z)
16 {
17     ++sum;
18     e[sum].from=x;
19     e[sum].to=y;
20     e[sum].len=z;
21 }
22 
23 bool comp(edge x,edge y)
24 {
25     return x.len<y.len;
26 }
27 
28 int find(int x)
29 {
30     if(x!=fa[x])fa[x]=find(fa[x]);
31     return fa[x];
32 }
33 
34 void un(int x,int y)
35 {
36     x=find(x);
37     y=find(y);
38     fa[x]=y;
39 }
40 
41 int main()
42 {
43     scanf("%d%d",&n,&m);
44     for(i=1;i<=m;++i)
45     {
46         scanf("%d%d%d",&x,&y,&z);
47         build(x,y,z);
48     }
49     sort(e+1,e+m+1,comp);
50     scanf("%d",&t);
51     for(int g=1;g<=t;++g)
52     {
53         scanf("%d%d",&st,&en);
54         ans1=inf;
55         ans2=0;
56         for(i=1;i<=m;++i)
57         {
58             minn=e[i].len;
59             maxn=inf;
60             for(j=1;j<=n;++j)fa[j]=j;
61             for(j=i;j<=m;++j)
62             {
63                 if(find(e[j].from)==find(e[j].to))continue;
64                 un(e[j].from,e[j].to);
65                 if(find(st)==find(en))
66                 {
67                     maxn=e[j].len;
68                     if(maxn-minn<ans1-ans2)
69                     {
70                         ans1=maxn;
71                         ans2=minn;
72                     }
73                     break;
74                 }
75             }
76         }
77         if(ans1==inf)printf("-1
");
78         else
79         printf("%d
",ans1-ans2);
80     }
81     return 0;
82 }

——Etta