https://www.acmicpc.net/problem/1865
알고리즘 분류
- 그래프 이론
- 벨만-포드
문제 파악
위의 캡처에서 알 수 있듯이 "시간이 뒤로 가게 된다"라는 문구로 유추해보면 음수 가중치가 존재한다는 것을 알 수 있고 벨만-포드 알고리즘을 활용하여 문제를 풀어야겠다고 접근했다.
추가로 다익스트라, 벨만-포드 알고리즘 중에서 왜 벨만-포드를 선택해야 하는지 궁금했는데 아래 링크에 잘 설명이 되어있어 참조 링크를 달아놓는다.
https://hy38.github.io/why-dijkstra-fail-on-a-negative-weighted-edge
더보기
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
static final int INF = Integer.MAX_VALUE/10;
static ArrayList<Edge> edge;
static int[] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));
int TC = Integer.parseInt(br.readLine());
while(TC-->0)
{
String[] firstLine = br.readLine().split(" ");
int N = Integer.parseInt(firstLine[0]);
int M = Integer.parseInt(firstLine[1]);
int W = Integer.parseInt(firstLine[2]);
edge = new ArrayList<>();
dist = new int[N+1];
Arrays.fill(dist,INF);
for(int idx =1; idx<=M;idx++)
{
String[] input = br.readLine().split(" ");
int S = Integer.parseInt(input[0]);
int E = Integer.parseInt(input[1]);
int T = Integer.parseInt(input[2]);
//무방향 그래프 이니까 시작점=>도착점 // 도착점=>시작점으로 추가
edge.add(new Edge(S,E,T));
edge.add(new Edge(E,S,T));
}
for(int idx = 1; idx<=W;idx++)
{
String[] input = br.readLine().split(" ");
int S = Integer.parseInt(input[0]);
int E = Integer.parseInt(input[1]);
int T = Integer.parseInt(input[2]) * -1;
//웜홀은 유방향
edge.add(new Edge(S,E,T));
}
for(int j=1;j<=N;j++)
{
for(Edge e : edge){
dist[e.e] = Math.min(dist[e.e],(dist[e.s] + e.t));
}
}
boolean answer = false;
for(Edge e : edge){
if(dist[e.e] > dist[e.s] + e.t){
answer = true;
break;
}
}
if(answer){
bw.write("YES");
}else{
bw.write("NO");
}
bw.newLine();
}
bw.flush();
br.close();
}
private static class Edge
{
int s;
int e;
int t;
public Edge(int s, int e, int t){
this.s = s;
this.e = e;
this.t = t;
}
}
}
'PS' 카테고리의 다른 글
[Programmers] LV1 - 숫자 문자열과 영단어 (0) | 2021.07.12 |
---|---|
[Programmers] LV2 - 괄호 회전하기 (0) | 2021.07.11 |
[BOJ]11404번 : 플로이드 (0) | 2021.07.06 |
[Programmers] LV3 - 단어 변환 (0) | 2021.07.05 |
[Programmers] LV3 - 순위 (0) | 2021.07.03 |