π λ¬Έμ
π± μμ΄λμ΄
"μκ°μ΄ λλμκ°λ κ²½μ°" -> λ§μ½ μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ€λ©΄ 무νν μκ°μ λλ릴 μ μλ€
μ¦ κ·Έλν λ΄ μμ μ¬μ΄ν΄μ νλ³νκΈ° μν΄ λ²¨λ§ν¬λ μκ³ λ¦¬μ¦μ μ¬μ©ν΄μΌ νλ€!
벨λ§ν¬λ μκ³ λ¦¬μ¦μ μ΅λ¨κ±°λ¦¬λ₯Ό ꡬνλ μκ³ λ¦¬μ¦μ λλ€. μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ€λ©΄ κ³μ μ΅λ¨κ±°λ¦¬κ° μ λ°μ΄νΈλλ€λ νΉμ§μ΄ μκΈ° λλ¬Έμ
μ΄λ¬ν νΉμ§μ λ°νμΌλ‘ λ°Έ λ§ ν¬λ μκ³ λ¦¬μ¦ Nλ²κΉμ§ μ€ννμ λ λ§μ§λ§κΉμ§ μ΅λ¨κ±°λ¦¬κ° μ λ°μ΄νΈλλ€λ©΄
μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ€λ κ²μ μ¦λͺ ν μ μλ€.
μ κ·Έλνλ μμ μ λ ₯ 2λ²μ ν λλ‘ λ§λ κ·Έλνμ κ°μ€μΉμ΄λ€. λ°Έλ§ν¬λ μκ³ λ¦¬μ¦μ Nλ²κΉμ§ μ€νν΄ λ³΄μ
1ν μ°¨ : 1(-2) / 2(4) / 3(0)
2ν μ°¨ : 1(-4) / 2(2) / 3(-2)
3ν μ°¨ : 1(-6) / 2(0) / 3(-4)
μ΄λ κ² μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νκΈ° λλ¬Έμ κ° λ Έλκ° κ³μ μ΅μκ°μΌλ‘ μ λ°μ΄νΈλλ κ²μ νμΈν μ μλ€!!
μ΄λ¬ν μ리λ₯Ό μ΄μ©ν΄μ 벨λ§ν¬λ μκ³ λ¦¬μ¦μ ꡬνν΄ λ³΄μ.
π± μ½λ λ° νμ΄
public class Main { | |
public static int N, M; | |
public static long INF = Long.MAX_VALUE; | |
public static ArrayList<ArrayList<node>> arr1; | |
public static long[] dist; | |
public static class node { // κ°μ μ 보 λ΄λ κ°μ²΄ | |
int goal, time; | |
public node(int goal, int time) { | |
this.goal = goal; | |
this.time = time; | |
} | |
} | |
public static boolean bellmanford(int start) { // λ°Έλ§ν¬λμκ³ λ¦¬μ¦ | |
Arrays.fill(dist, INF); | |
dist[start] = 0; | |
boolean isNegative = false; | |
for (int i = 0; i < N; i++) { | |
isNegative = false; | |
for (int j = 0; j < N; j++) { | |
for (node nd : arr1.get(j)) { | |
if (dist[j] != INF && dist[nd.goal] > dist[j] + nd.time) { | |
dist[nd.goal] = dist[j] + nd.time; | |
isNegative = true; | |
if (i == N - 1) { | |
// λ§μ§λ§κΉμ§ μ΄κΈ°ν λλ€λ©΄ μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ€. | |
return true; | |
} | |
} | |
} | |
} | |
if (!isNegative) { | |
// μ΄κΈ°νκ° λμ§ μμλ€λ©΄ μμ μ¬μ΄ν΄ μ‘΄μ¬ x | |
break; | |
} | |
} | |
return isNegative; | |
} | |
public static void main(String[] args) throws IOException { //쑰건 μ λ ₯ | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
StringTokenizer st = new StringTokenizer(br.readLine(), " "); | |
StringBuilder sb = new StringBuilder(); | |
N = Integer.parseInt(st.nextToken()); | |
M = Integer.parseInt(st.nextToken()); | |
arr1 = new ArrayList<>(); | |
dist = new long[N]; // 6000*10000*N = intν λ²μ λ²μ΄λ¨ | |
for (int i = 0; i < N; i++) { | |
arr1.add(new ArrayList<>()); | |
} | |
for (int i = 0; i < M; i++) { | |
st = new StringTokenizer(br.readLine(), " "); | |
int s = Integer.parseInt(st.nextToken()) - 1; | |
int e = Integer.parseInt(st.nextToken()) - 1; | |
int t = Integer.parseInt(st.nextToken()); | |
arr1.get(s).add(new node(e, t)); | |
} | |
// μΆλ ₯ | |
if (bellmanford(0)) { | |
sb.append(-1); | |
} else { | |
for (int i = 1; i < N; i++) { | |
sb.append(dist[i] == INF ? -1 : dist[i]).append("\n"); | |
} | |
} | |
System.out.print(sb); | |
} | |
} |
κ°μ₯ κΈ°λ³Έμ μΈ ννμ 벨λ§ν¬λ μκ³ λ¦¬μ¦μ΄λ€. λ§μ§λ§κΉμ§ μ λ°μ΄νΈλλ€λ©΄ μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ€λ κ²μ΄κ³
λ§μ§λ§κΉμ§ μ€νλκΈ° μ΄μ μ λͺ¨λ λ Έλκ° μ λ°μ΄νΈλμ§ μμλ€λ©΄ μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νμ§ μλ κ²μ΄λ€.
μ΄λ¬ν νλ³μ isNegativeμμ true / falseλ‘ νμ°¨λ§λ€ νλ¨νλ€!
π± λλ μ
벨λ§ν¬λ μκ³ λ¦¬μ¦ μ λ¬Έλ¬Έμ λ‘ κ°μ₯ μ’μ κ² κ°λ€! 벨λ§ν¬λλ₯Ό μ΄μ©ν΄μ μμ μ¬μ΄ν΄μ νλ¨νλ€λ μ νμ λκ²
μ μ νκ³ , μλ‘μ΄ κ²½νμ΄μλ€
'Algorithm > - Baekjoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] λ°±μ€ 1781 μ»΅λΌλ©΄ (JAVA) (2) | 2024.02.27 |
---|---|
[BOJ] λ°±μ€ 1976 μ¬ν κ°μ (JAVA) (4) | 2024.02.26 |
[BOJ] λ°±μ€ 17836 곡주λμ ꡬν΄λΌ! (JAVA) (2) | 2024.02.13 |
[BOJ] λ°±μ€ 2290 LCD Test (JAVA) (0) | 2024.02.05 |
[BOJ] λ°±μ€ 2096 λ΄λ €κ°κΈ° (JAVA) (1) | 2024.01.29 |
λλ§μ κ°λ° λ°μ΄ν°λ² μ΄μ€!
ν¬μ€ν μ΄ μ’μλ€λ©΄ "μ’μμβ€οΈ" λλ "ꡬλ ππ»" ν΄μ£ΌμΈμ!