首页 > 代码库 > HDU1598 find the most comfortable road
HDU1598 find the most comfortable road
题目描述:
XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。
输入：
输入包括多个测试实例，每个实例包括：
第一行有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, 表示寻路的起终点。
输出：
每个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。
看风神的BLOG里面推荐的并查集题目做的这道题，这道题算是并查集的一道提升题。自己的思路就是枚举+并查集，先对输入的speed排序一遍，然后对排过序的所有边的可能组合进行枚举，即两个for循环就可解决，然后更新最小值即可。
可能是自己的算法还不够好吧，最后跑了765ms险过，等自己提升之后可以尝试优化自己的算法。
1 #include <iostream> 2 #include <iomanip> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <algorithm> 6 #include <functional> 7 #include <vector> 8 #include <cmath> 9 #include <string>10 #include <stack> 11 #include <queue>12 using namespace std;13 int n , m , father[1005];14 struct P{15 int start , end , speed;16 }p[1005];17 bool cmp(P a , P b)18 {19 return b.speed > a.speed;20 }21 void init()22 { //并查集的初始化函数23 for(int i = 1 ; i <= n ; i++)24 father[i] = i;25 }26 int getf(int v) 27 { //找点v的祖先28 return father[v] = (v == father[v]) ? v : getf(father[v]);29 }30 void merge(int x , int y)31 { //直接用路径压缩进行合并32 int a , b;33 a = getf(x);34 b = getf(y);35 if(a != b)36 father[b] = a;37 }38 int main()39 {40 int Q , i , j , k , x , y;41 while(~scanf("%d %d",&n,&m))42 {43 for(i = 1 ; i <= m ; i++)44 scanf("%d %d %d",&p[i].start,&p[i].end,&p[i].speed);45 sort(p+1 , p+1+m , cmp);46 scanf("%d",&Q);47 while(Q--) {48 int min = INT_MAX;49 scanf("%d %d",&x,&y);50 for(i = 1 ; i <= m ; i++) {51 init(); //每次都还要初始化52 for(j = i ; j <= m ; j++) {53 merge(p[j].start , p[j].end);54 if(getf(x) == getf(y)) { //此时说明x 和 y是连通的 55 int ans = p[j].speed - p[i].speed; //j >= i ，p[j]自然大于p[i]56 if(min > ans) //更新最小值57 min = ans;58 } else {59 continue;60 }61 } 62 }63 if(min == INT_MAX) { //说明没有边连通64 printf("-1\n");65 } else {66 printf("%d\n",min);67 }68 }69 }70 return 0;71 }
HDU1598 find the most comfortable road
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。