NC229577. 阿强的路
描述
输入描述
第一行两个整数n,m，分别表示无向图的点数和边数。
第二行n个正整数，第i个正整数表示点i的点权。
接下来m行每行三个正整数，分别描述一条边的两个端点和边权。
输出描述
共n行，每行n个整数，第i行第j个整数表示从i到j的路径的最小权值，如果从i不能到达j，则该值为-1。特别地，当i=j时输出0。
示例1
输入:
3 3 2 3 3 1 2 2 2 3 3 1 3 1
输出:
0 6 3 6 0 6 3 6 0
C++(clang++ 11.0.1) 解法, 执行用时: 286ms, 内存消耗: 8556K, 提交时间: 2022-10-10 14:08:12
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
const int mod = 1e9+7;
int f[N][N],g[N][N];
int a[N];
signed main(void){
ios::sync_with_stdio(false);cin.tie(0);
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
int n,m;
cin>>n>>m;
vector<int>idx(n);
for(int i=1;i<=n;i++) cin>>a[i],idx[i-1]=i,f[i][i]=g[i][i]=0;
sort(idx.begin(),idx.end(),[&](int x,int y){return a[x]<a[y];});
while(m--){
int u,v,w;
cin>>u>>v>>w;
g[u][v]=g[v][u]=min(g[u][v],w);
f[u][v]=f[v][u]=min(f[u][v],g[u][v]*max(a[u],a[v]));
}
for(auto k:idx)
for(auto i:idx)
for(auto j:idx)
if(g[i][j]>max(g[i][k],g[k][j])){
g[i][j]=g[j][i]=max(g[i][k],g[k][j]);
f[i][j]=f[j][i]=min(f[i][j],g[i][j]*max({a[i],a[j],a[k]}));
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cout<<f[i][j]<<" ";
cout<<"\n";
}
return 0;
}