手机怎么建立网站,做百科网站,微网站建设包含哪些内容,网站建设项目申报书旅行
ssl 1312
题目大意#xff1a;
有一个图#xff0c;要从一个点到另一个点#xff0c;问路上的最大值和最小值的比最小是多少
原题#xff1a;
题目描述
Z小镇是一个景色宜人的地方#xff0c;吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点#xff…旅行
ssl 1312
题目大意
有一个图要从一个点到另一个点问路上的最大值和最小值的比最小是多少
原题
题目描述
Z小镇是一个景色宜人的地方吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点编号为1,2,3,…,N这些景点被M条道路连接着所有道路都是双向的两个景点之间可能有多条道路。也许是为了保护该地的旅游资源Z小镇有个奇怪的规定就是对于一条给定的公路Ri任何在该公路上行驶的车辆速度必须为Vi。速度变化太快使得游客们很不舒服因此从一个景点前往另一个景点的时候大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线也就是所谓最舒适的路线。
输入
第一行包含两个正整数N和M。 接下来的M行每行包含三个正整数xy和v。表示景点x到景点y之间有一条双向公路车辆必须以速度v在该公路上行驶。 最后一行包含两个正整数st表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。
输出
如果景点s到景点t没有路径输出“IMPOSSIBLE”。否则输出一个数表示最小的速度比。如果需要输出一个既约分数。
输入样例
样例1
4 2
1 2 1
3 4 2
1 4样例
3 3
1 2 10
1 2 5
2 3 8
1 3样例3
3 2
1 2 2
2 3 4
1 3输出样例
样例1
IMPOSSIBLE样例2
5/4样例3
2数据范围
1N500 1x,yN0v30000x≠y 0M5000
解题思路
首先枚举最小速度然后再跑最小生成树要提前排序然后求比最后求min
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,m,s,t,g,h,x1,y1,sum,dad[505];
double ans;
bool pd;
struct rec
{int x,y,l;
}a[5005];
int read()//快读
{char xx;int o0;xxgetchar();while (xx0||xx9) xxgetchar();while (xx0xx9){oo*10xx-48;xxgetchar();}return o;
}
bool cmp(rec aa,rec bb){return aa.lbb.l;}
int find(int dep){return dad[dep]dep?dep:dad[dep]find(dad[dep]);}
int main()
{nread();mread();for (int i1;im;i)a[i](rec){read(),read(),read()};//读入sread();tread();sort(a1,a1m,cmp);ans2147483647;for (int i1;im;i){for (int j1;jn;j)dad[j]j;//预处理sum2147483647;for (int ji;jm;j){x1find(a[j].x);//求根节点y1find(a[j].y);if (x1!y1) dad[min(x1,y1)]max(x1,y1);//合并if (find(s)find(t))//判断{pdtrue;suma[j].l;//记录break;}}if (ans(double)sum/(double)a[i].lpd){ans(double)sum/(double)a[i].l;//求最小值gsum;//记录ha[i].l;}}if (ans!2147483647){if (g%h0) printf(%d,g/h);//整数else printf(%d/%d,g/__gcd(g,h),h/__gcd(g,h)); //求分数}else printf(IMPOSSIBLE);
}
