[伯俊]1404号フロイド/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
25.最短経路
図形の幹線に重みがない場合は、BFSを使用して最短距離を検索できます.重みがあればどうなりますか?
Java/Python
5.フロイド
11404号
FloydとShellアルゴリズムの問題を学ぶ
これは、AからBまでのコストの最大値を求めることができるすべての都市ペア(A、B)に関するプログラムです.
floodとshallアルゴリズムを使用!
import java.io.*;
import java.util.*;
public class Main {
static final int INF = 1000000000;
static int[][] dist;
static int cityCnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = null;
cityCnt = Integer.parseInt(br.readLine());
int busCnt = Integer.parseInt(br.readLine());
dist = new int[cityCnt + 1][cityCnt + 1];
for(int i = 1; i <= cityCnt; i++){
for(int j = 1; j <= cityCnt; j++){
if(i != j) dist[i][j] = INF;
}
}
while(busCnt-- > 0){
// 입력값 초기화
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
dist[start][end] = Math.min(dist[start][end], time);
}
floydWarshall();
StringBuilder sb = new StringBuilder();
for(int i=1; i <= cityCnt; i++) {
for(int j=1; j <= cityCnt; j++) {
if(dist[i][j] >= INF) sb.append("0 ");
else sb.append(dist[i][j] + " ");
}
sb.append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static void floydWarshall() {
// 기준 K
for(int k = 1; k <= cityCnt; k++) {
// 출발 노드 i
for(int i = 1; i <= cityCnt; i++) {
// 도착 노드 j
for(int j = 1; j <= cityCnt; j++) {
//i -> k , k -> j 가는 거리, i -> j 가는 거리를 비교 (작은 값 : 최소거리)
dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
}
}
}
}
}
import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
INF = 10000000000
city = [[INF] * N for i in range(N)]
for i in range(M):
a, b, c = map(int, sys.stdin.readline().split())
if city[a - 1][b - 1] > c:
city[a - 1][b - 1] = c
for k in range(N):
for i in range(N):
for j in range(N):
if i != j and city[i][j] > city[i][k] + city[k][j]:
city[i][j] = city[i][k] + city[k][j]
for i in city:
for j in i:
if j == INF:
print(0, end=' ')
else:
print(j, end=' ')
print()
Reference
この問題について([伯俊]1404号フロイド/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-11404번-플로이드-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol