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

分手后的思念是犯贱 2023-08-17 16:25 77阅读 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 条评论，77人围观）

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

相关阅读

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

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

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

相关分治法求最大最小值

分治法是一种递归的问题解决方法，它将一个大问题划分为多个小问题，然后逐个解决这些小问题，最后将结果合并得到最终的解决方案。对于求最大最小值的问题，可以使用分治法来解决。以下

绝地灬酷狼/ 2024年02月20日 12:42/ 0 赞/ 61 阅读

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

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

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

相关【leetcode】python求矩阵中的最小路径之和和输出最小路径

python求矩阵中的最小路径之和和输出最小路径 1、求最小路径之和，并且输出最小路径 > 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路

今天药忘吃喽~/ 2022年12月08日 14:12/ 0 赞/ 114 阅读

相关求数组最大值最小值

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

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

相关 leetcode687最长同值路径

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

曾经终败给现在/ 2022年09月03日 12:24/ 0 赞/ 145 阅读

相关分治法求最大最小值

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

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

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

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

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

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

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

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

相关 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 赞/ 321 阅读