2021辽宁省大学生程序设计竞赛（正式赛）阿强的路 Floyd最短路、思维

题目分析：题目给定一个无向图，要求回答对于给定两点 A , B A,B A,B之间路径最大点权 × \times ×路径最大边权的最小值

很显然是一个多源路径问题，首先要维护边集数组，由于需要计算一个最大点权，一个最大边权，两个最大不好同时处理，因此将点集数组按照权值进行排序，这样可以保证求到“最大值的最小值”，即遍历到大于当前答案的第一个值立即更新掉。

用一个 d p dp dp数组表示 d p [ i ] [ j ] dp[i][j] dp[i][j]为"最小的路径最大点权乘以路径最大边权"，并将其初始化为 u v uv uv间权值 × \times × u 、 v u、v u、v之间较大的权值。然后按照 F l o y d Floyd Floyd的思路不断更新下去求多源最短路即可。

#include 
#define ll long long
using namespace std;

const int N = 510;

struct node{
    int ser; ll w; 
    const bool operator n >> m;
    memset(edge, 0x3f, sizeof(edge));
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 1; i > a[i].w;
        a[i].ser = i, b[i] = a[i].w;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1, u, v, w; i > u >> v >> w;
        edge[u][v] = edge[v][u] = 1ll * w;
        dp[u][v] = dp[v][u] = min(dp[u][v], edge[u][v] * max(b[u], b[v]));
    }
    for(int i = 1; i