P1744 采购特价商品网页链接P1744 采购特价商品题目背景《爱与愁的故事第三弹·shopping》第一章。题目描述中山路店山店海成了购物狂爱与愁大神的“不归之路”。中山路上有n nnn ≤ 100 n \leq 100n≤100家店每家店的坐标均在− 10000 -10000−10000至10000 1000010000之间。其中的m mm家店之间有通路。若有通路则表示可以从一家店走到另一家店通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗输入格式共n m 3 nm3nm3行第一行整数n nn。接下来n nn行每行两个整数x xx和y yy描述了一家店的坐标。接下来一行整数m mm。接下来m mm行每行描述一条通路由两个整数i ii和j jj组成表示第i ii家店和第j jj家店之间有通路。接下来一行两个整数s ss和t tt分别表示原点和目标店。输出格式仅一行一个实数保留两位小数表示从s ss到t tt的最短路径长度。输入输出样例 #1输入 #15 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5输出 #13.41说明/提示对于100 % 100 \%100%的数据2 ≤ n ≤ 100 2 \le n \leq 1002≤n≤1001 ≤ i , j , s , t ≤ n 1 \le i, j, s, t \le n1≤i,j,s,t≤n1 ≤ m ≤ 1000 1 \le m \leq 10001≤m≤1000。解题思路本题是图论最短路的经典应用。将每家店看作图中的一个节点若两家店之间有通路则在这两个节点之间连一条无向边边权为两点之间的欧几里得距离。问题转化为求从起点店s ss到目标店t tt的最短路径长度。由于节点数n ≤ 100 n \le 100n≤100边数m ≤ 1000 m \le 1000m≤1000可以使用 Floyd 算法求出所有节点对之间的最短距离然后直接输出s ss到t tt的距离。1. 问题等价转化输入给出n nn家店的坐标( x i , y i ) (x_i, y_i)(xi,yi)以及m mm条通路。对于每条通路( i , j ) (i, j)(i,j)计算两点间的直线距离d ( i , j ) ( x i − x j ) 2 ( y i − y j ) 2 d(i,j) \sqrt{(x_i - x_j)^2 (y_i - y_j)^2}d(i,j)(xi−xj)2(yi−yj)2由于是无向通路所以d ( i , j ) d ( j , i ) d(i,j) d(j,i)d(i,j)d(j,i)。目标是求从s ss到t tt的最短路径长度。图中有n ≤ 100 n \le 100n≤100个节点边权非负适合使用 Floyd 算法进行全源最短路计算。2. 算法实现初始化距离矩阵创建一个n × n n \times nn×n的二维数组d所有元素初始化为一个极大值如2020040222 20200402222020040222表示不可达。读入坐标将每家店的横纵坐标分别存入X[i]和Y[i]。读入通路并建边对于每条通路( u , v ) (u, v)(u,v)计算两点间的欧几里得距离赋值给d[u][v]和d[v][u]。读入起点和终点得到s和t。Floyd 算法求最短路三重循环枚举中间点k、起点i、终点j。状态转移d[i][j] min(d[i][j], d[i][k] d[k][j])。输出结果输出d[s][t]保留两位小数。3. 复杂度分析时间复杂度Floyd 算法需要三重循环复杂度为O ( n 3 ) O(n^3)O(n3)。n ≤ 100 n \le 100n≤100运算量约10 6 10^6106非常快。空间复杂度需要存储n × n n \times nn×n的距离矩阵复杂度O ( n 2 ) O(n^2)O(n2)空间消耗很小。总结将商店和通路抽象为带权无向图边权为两点间的欧几里得距离。由于节点数很少直接使用 Floyd 算法求出所有点对的最短路径最后输出起点到终点的距离即可。该方法简单直观代码实现容易适合本题数据规模。代码简要说明d[N][N]距离矩阵初始化为极大值。X[N], Y[N]存储每个店的坐标。读入n nn后初始化距离矩阵读入坐标读入m mm条通路计算距离并更新矩阵。读入s , t s, ts,t。三重循环执行 Floyd 算法更新所有点对的最短距离。printf(%.2lf, d[s][t])输出结果保留两位小数。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1100;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,s,t;ll u,v;doubled[N][N];doubleX[N],Y[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i)for(ll j1;jn;j)d[i][j]2020040222;for(ll i1;in;i)cinX[i]Y[i];cinm;for(ll i1;im;i){cinuv;d[u][v]d[v][u]sqrt((X[u]-X[v])*(X[u]-X[v])(Y[u]-Y[v])*(Y[u]-Y[v]));}cinst;for(ll k1;kn;k)for(ll i1;in;i)for(ll j1;jn;j)d[i][j]min(d[i][j],d[i][k]d[k][j]);printf(%.2lf,d[s][t]);return0;}
P1744 采购特价商品网页链接P1744 采购特价商品题目背景《爱与愁的故事第三弹·shopping》第一章。题目描述中山路店山店海成了购物狂爱与愁大神的“不归之路”。中山路上有n nnn ≤ 100 n \leq 100n≤100家店每家店的坐标均在− 10000 -10000−10000至10000 1000010000之间。其中的m mm家店之间有通路。若有通路则表示可以从一家店走到另一家店通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗输入格式共n m 3 nm3nm3行第一行整数n nn。接下来n nn行每行两个整数x xx和y yy描述了一家店的坐标。接下来一行整数m mm。接下来m mm行每行描述一条通路由两个整数i ii和j jj组成表示第i ii家店和第j jj家店之间有通路。接下来一行两个整数s ss和t tt分别表示原点和目标店。输出格式仅一行一个实数保留两位小数表示从s ss到t tt的最短路径长度。输入输出样例 #1输入 #15 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5输出 #13.41说明/提示对于100 % 100 \%100%的数据2 ≤ n ≤ 100 2 \le n \leq 1002≤n≤1001 ≤ i , j , s , t ≤ n 1 \le i, j, s, t \le n1≤i,j,s,t≤n1 ≤ m ≤ 1000 1 \le m \leq 10001≤m≤1000。解题思路本题是图论最短路的经典应用。将每家店看作图中的一个节点若两家店之间有通路则在这两个节点之间连一条无向边边权为两点之间的欧几里得距离。问题转化为求从起点店s ss到目标店t tt的最短路径长度。由于节点数n ≤ 100 n \le 100n≤100边数m ≤ 1000 m \le 1000m≤1000可以使用 Floyd 算法求出所有节点对之间的最短距离然后直接输出s ss到t tt的距离。1. 问题等价转化输入给出n nn家店的坐标( x i , y i ) (x_i, y_i)(xi,yi)以及m mm条通路。对于每条通路( i , j ) (i, j)(i,j)计算两点间的直线距离d ( i , j ) ( x i − x j ) 2 ( y i − y j ) 2 d(i,j) \sqrt{(x_i - x_j)^2 (y_i - y_j)^2}d(i,j)(xi−xj)2(yi−yj)2由于是无向通路所以d ( i , j ) d ( j , i ) d(i,j) d(j,i)d(i,j)d(j,i)。目标是求从s ss到t tt的最短路径长度。图中有n ≤ 100 n \le 100n≤100个节点边权非负适合使用 Floyd 算法进行全源最短路计算。2. 算法实现初始化距离矩阵创建一个n × n n \times nn×n的二维数组d所有元素初始化为一个极大值如2020040222 20200402222020040222表示不可达。读入坐标将每家店的横纵坐标分别存入X[i]和Y[i]。读入通路并建边对于每条通路( u , v ) (u, v)(u,v)计算两点间的欧几里得距离赋值给d[u][v]和d[v][u]。读入起点和终点得到s和t。Floyd 算法求最短路三重循环枚举中间点k、起点i、终点j。状态转移d[i][j] min(d[i][j], d[i][k] d[k][j])。输出结果输出d[s][t]保留两位小数。3. 复杂度分析时间复杂度Floyd 算法需要三重循环复杂度为O ( n 3 ) O(n^3)O(n3)。n ≤ 100 n \le 100n≤100运算量约10 6 10^6106非常快。空间复杂度需要存储n × n n \times nn×n的距离矩阵复杂度O ( n 2 ) O(n^2)O(n2)空间消耗很小。总结将商店和通路抽象为带权无向图边权为两点间的欧几里得距离。由于节点数很少直接使用 Floyd 算法求出所有点对的最短路径最后输出起点到终点的距离即可。该方法简单直观代码实现容易适合本题数据规模。代码简要说明d[N][N]距离矩阵初始化为极大值。X[N], Y[N]存储每个店的坐标。读入n nn后初始化距离矩阵读入坐标读入m mm条通路计算距离并更新矩阵。读入s , t s, ts,t。三重循环执行 Floyd 算法更新所有点对的最短距离。printf(%.2lf, d[s][t])输出结果保留两位小数。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1100;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,s,t;ll u,v;doubled[N][N];doubleX[N],Y[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i)for(ll j1;jn;j)d[i][j]2020040222;for(ll i1;in;i)cinX[i]Y[i];cinm;for(ll i1;im;i){cinuv;d[u][v]d[v][u]sqrt((X[u]-X[v])*(X[u]-X[v])(Y[u]-Y[v])*(Y[u]-Y[v]));}cinst;for(ll k1;kn;k)for(ll i1;in;i)for(ll j1;jn;j)d[i][j]min(d[i][j],d[i][k]d[k][j]);printf(%.2lf,d[s][t]);return0;}
