Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
Tags
- PS
- 자바PS
- 백준코딩테스트
- YBMCOS
- 백준
- BFS
- 네트워크플로우
- 다이나믹프로그래밍
- 시뮬레이션
- spring
- GatherTown
- 구현
- 알고리즘
- QUICKSTARTGUIDE
- 우선순위큐
- 이젠 골드구현도 어렵네..
- 재귀함수
- 다익스트라
- 세그먼트트리
- 게더타운시작
- DFS
- java
- 취득후기
- 완전탐색
- COSPRO
- deque
- COSPROJAVA1급
- dp
- 엘라스틱서치
- 01BFS
Archives
- Today
- Total
공부공간
BOJ - 1238 ) 파티 본문
https://www.acmicpc.net/problem/1238
N개의 노드에서 다시 자신의 노드로 돌아오는데에 최댓값을 구하는 문제이다.
1~N까지 Floye-Warshall 알고리즘을 통해 최단경로를 구해놓고,
map[x][i] + map[i][x] 의 값이 가장 큰 사람을 출력한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 파티 {
// 플로이드워셜
// 모든 최단거리중 가장 많이 시간을 소비하는 사람 출력
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int map[][] = new int[n+1][n+1];
for(int i= 1 ; i <=n ; i++) {
for(int j = 1 ; j <=n ; j ++) {
map[i][j] =987654321;
}
map[i][i] =0;
}
for(int i = 0 ; i < m ; i ++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b= Integer.parseInt(st.nextToken());
map[a][b] = Integer.parseInt(st.nextToken());
}
for(int mid = 1 ; mid <= n ;mid++) {
for(int start =1 ; start <=n ; start++) {
for(int end=1; end<=n ; end++) {
{
if(map[start][end] > map[start][mid] + map[mid][end]) {
map[start][end] = map[start][mid] + map[mid][end];
}
}
}
}
}
int ans = -1;
for(int i= 1 ; i <=n ; i++) {
if(map[i][x] + map[x][i] > ans) {
ans = map[i][x] + map[x][i];
}
}
System.out.println(ans);
}
}
'알고리즘 > Floyd-Warshall' 카테고리의 다른 글
프로그래머스 ) 순위 (0) | 2020.09.06 |
---|
Comments