当前位置:网站首页>[shortest circuit] acwing1128 Messenger: Floyd shortest circuit
[shortest circuit] acwing1128 Messenger: Floyd shortest circuit
2022-07-07 11:46:00 【Twilight_ years】
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);
}
}
边栏推荐
- Flet教程之 14 ListTile 基础入门(教程含源码)
- VIM command mode and input mode switching
- Flet教程之 17 Card卡片组件 基础入门(教程含源码)
- Swiftui swift internal skill: five skills of using opaque type in swift
- 大佬们有没有人遇到过 flink oracle cdc,读取一个没有更新操作的表,隔十几秒就重复读取
- 【滤波跟踪】基于matlab捷联惯导仿真【含Matlab源码 1935期】
- Audit migration
- electron 添加 SQLite 数据库
- 0.96 inch IIC LCD driver based on stc8g1k08
- Learning notes | data Xiaobai uses dataease to make a large data screen
猜你喜欢
【滤波跟踪】基于matlab扩展卡尔曼滤波EKF和无迹卡尔曼滤波UKF比较【含Matlab源码 1933期】
Table replication in PostgreSQL
技术分享 | 抓包分析 TCP 协议
Apprentissage comparatif non supervisé des caractéristiques visuelles par les assignations de groupes de contrôle
科普达人丨一文弄懂什么是云计算?
Flet教程之 17 Card卡片组件 基础入门(教程含源码)
清华姚班程序员,网上征婚被骂?
SwiftUI 教程之如何在 2 秒内实现自动滚动功能
OneDNS助力高校行业网络安全
Unsupervised learning of visual features by contracting cluster assignments
随机推荐
LeetCode - 面试题17.24 最大子矩阵
超标量处理器设计 姚永斌 第10章 指令提交 摘录
基于华为云IOT设计智能称重系统(STM32)
Verilog realizes nixie tube display driver [with source code]
Leetcode - interview question 17.24 maximum submatrix
【滤波跟踪】基于matlab捷联惯导仿真【含Matlab源码 1935期】
Unsupervised learning of visual features by contracting cluster assignments
千人规模互联网公司研发效能成功之路
【最短路】ACwing 1127. 香甜的黄油(堆优化的dijsktra或spfa)
Verilog design responder [with source code]
Reasons for the failure of web side automation test
There are ways to improve self-discipline and self-control
In depth learning autumn recruitment interview questions collection (1)
【紋理特征提取】基於matlab局部二值模式LBP圖像紋理特征提取【含Matlab源碼 1931期】
Nuclear boat (I): when "male mothers" come into reality, can the biotechnology revolution liberate women?
R language uses image of magick package_ Mosaic functions and images_ The flatten function stacks multiple pictures together to form a stack layers on top of each other
The database synchronization tool dbsync adds support for mongodb and es
Android 面试知识点
Table replication in PostgreSQL
科普达人丨一文弄懂什么是云计算?