当前位置:网站首页>【最短路】Acwing1128信使:floyd最短路
【最短路】Acwing1128信使:floyd最短路
2022-07-07 09:46:00 【暮色_年华】
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static final int N=1000;
static final int INF=(int)1e8;
static int[][] dist=new int[N][N];
static int n,m;
public static void main(String[]args)throws IOException{
String[] s=br.readLine().split(" ");
n=Integer.parseInt(s[0]);
m=Integer.parseInt(s[1]);
for(int i=1;i<=n;i++)
Arrays.fill(dist[i],INF);
for(int i=1;i<=n;i++){
dist[i][i]=0;
}
for(int i=0;i<m;i++){
s=br.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
int c=Integer.parseInt(s[2]);
dist[a][b]=dist[b][a]=Math.min(dist[a][b],c);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(dist[1][i],res);
}
if(res>INF/2)System.out.println(-1);
else System.out.println(res);
}
}
边栏推荐
- 软件设计之——“高内聚低耦合”
- 0.96 inch IIC LCD driver based on stc8g1k08
- Zhou Yajin, a top safety scholar of Zhejiang University, is a curiosity driven activist
- 关于测试人生的一站式发展建议
- JS add spaces to the string
- Excel公式知多少?
- 聊聊SOC启动(十) 内核启动先导知识
- 通过环境变量将 Pod 信息呈现给容器
- What is high cohesion and low coupling?
- R语言使用quantile函数计算评分值的分位数(20%、40%、60%、80%)、使用逻辑操作符将对应的分位区间(quantile)编码为分类值生成新的字段、strsplit函数将学生的名和姓拆分
猜你喜欢
相机标定(1): 单目相机标定及张正友标定基本原理
90后,辞职创业,说要卷死云数据库
electron添加SQLite数据库
Talk about SOC startup (x) kernel startup pilot knowledge
Talk about SOC startup (VII) uboot startup process III
About how to install mysql8.0 on the cloud server (Tencent cloud here) and enable local remote connection
千人规模互联网公司研发效能成功之路
Technology sharing | packet capturing analysis TCP protocol
Solve the problem that vscode can only open two tabs
核舟记(一):当“男妈妈”走进现实,生物科技革命能解放女性吗?
随机推荐
EasyUI learn to organize notes
Electron adding SQLite database
Reasons for the failure of web side automation test
Verilog design responder [with source code]
[question] Compilation Principle
Talk about SOC startup (11) kernel initialization
‘module‘ object is not callable错误
请查收.NET MAUI 的最新学习资源
Avoid mutating a prop directly since the value will be overwritten whenever the parent component
Eth trunk link switching delay is too high
常用sql语句整理:mysql
Half of the people don't know the difference between for and foreach???
Easyui学习整理笔记
Apprentissage comparatif non supervisé des caractéristiques visuelles par les assignations de groupes de contrôle
OneDNS助力高校行业网络安全
sink 消费 到 MySQL, 数据库表里面已经设置了 自增主键, flink 里面,如何 操作?
相机标定(2): 单目相机标定总结
Debezium同步之Debezium架构详解
The running kubernetes cluster wants to adjust the network segment address of pod
聊聊SOC启动(九) 为uboot 添加新的board