【p2888】求路径的最长边可取的最小值

分手后的思念是犯贱 2023-08-17 16:25 127阅读 0赞

题意：有很多条路径，每条路径有最长的边x，选取x最小的情况作为答案

代码：

1.Floyd写法：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define LL long long
    #define maxn 302
    #define inf 0x3f3f3f3f
    using namespace std;
    int mp[maxn][maxn];
    int main(){
        int n,m,t;
        scanf("%d%d%d",&n,&m,&t);    
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            mp[i][j]=inf;
        mp[i][i]=0;
        }    
        int a,b,c;
        for(int i=1;i<=m;i++){
            cin>>a>>b>>c;
            mp[a][b]=c;
        }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i!=j&&i!=k&&j!=k&&mp[i][k]!=inf&&mp[k][j]!=inf)
            mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));
        }
        for(int i=1;i<=t;i++){
            cin>>a>>b;
            if(mp[a][b]==inf)
            cout<<"-1"<<endl;
            else
            cout<<mp[a][b]<<endl;
        }
    }

2.SPFA写法（记录询问去避免TLE）

转载于:https://www.cnblogs.com/Aiahtwo/p/11519920.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/4e1ab0d9a10d48a9ad89f6ffa237f9e2.png

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关求数组的最大值和最小值函数

在 python 中，可以使用 numpy 库中的函数 numpy.max() 和 numpy.min() 来求数组的最大值和最小值。示例： import num

你的名字/ 2024年03月25日 17:20/ 0 赞/ 171 阅读

相关【p2888】求路径的最长边可取的最小值

题意：有很多条路径，每条路径有最长的边x，选取x最小的情况作为答案代码： 1.Floyd写法： ![ContractedBlock.gif][] ![ExpandedB

分手后的思念是犯贱/ 2023年08月17日 16:25/ 0 赞/ 128 阅读

相关求列表的最大值和最小值及其索引

c = [-10,-5,0,5,3,10,15,-20,25] print c.index(min(c)) 返回最小值 print c.i

水深无声/ 2023年07月15日 09:29/ 0 赞/ 125 阅读

相关求数组中的最大最小值

求数组中最大最小值的几种方法：问题分解法：遍历两次数组，反别求出最大值和最小值取单元素法：两个变量，变量min标记最小值，变量max标记最大值，每次循环取出一

淡淡的烟草味﹌/ 2023年06月26日 05:36/ 0 赞/ 58 阅读

相关 mysql 求最小值/最大值

计算所有人最低工资和最高工资,需分别用到min()和max()函数。(请注意，MIN和MAX函数会忽略NULL值) 1 select min(sal) as min\_s

淩亂°似流年/ 2023年06月22日 03:25/ 0 赞/ 130 阅读

相关求数组最大值最小值

include <iostream> include <algorithm> using namespace std; in

古城微笑少年丶/ 2022年09月12日 01:44/ 0 赞/ 420 阅读

相关分治法求最大最小值

include<iostream> include<stdio.h> using namespace std; int max(int

系统管理员/ 2022年07月11日 12:22/ 0 赞/ 326 阅读

相关 JavaScript求数组的最大值与最小值

在JavaScript中，当要求一串数中的最大值或最小值时，可以使用Math.max()和Math.min()来实现，使用方法如下： Math.max(12, 15,

ゞ浴缸里的玫瑰/ 2022年05月09日 11:04/ 0 赞/ 378 阅读

相关 C++求容器中的最小最大值

// Visual Studio 2015编译通过 // 以std::vector容器为例 include <iostream> in

偏执的太偏执、/ 2022年01月25日 18:27/ 0 赞/ 458 阅读

相关 python 求数组a 的最大值和最小值

>>> a=[1,2,3,4,5,6,7,8,98,9] >>> print(max(a)) 98 >>> print(min(a))

比眉伴天荒/ 2022年01月10日 06:11/ 0 赞/ 432 阅读