문제

https://www.acmicpc.net/problem/14938

---

입력

첫째 줄에는 지역의 개수 n
수색범위 m
길의 개수 r

둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l

---

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

---

풀이

제한조건

• n (1 ≤ n ≤ 100)
• m (1 ≤ m ≤ 15)
• r (1 ≤ r ≤ 100)
• t (1 ≤ t ≤ 30)
• l (1 ≤ l ≤ 15)
• 지역의 번호는 1이상 n이하의 정수이다.
• 두 지역의 번호가 같은 경우는 없다.

접근방법

플로이드-워셜, 다익스트라
문제를 읽어보면, 가능한 모든 지점에서 거리를 살펴봐야함을 알 수 있다.

제한 조건을 고려하였을때, 크기가 충분히 작으므로, 플로이드-워셜 알고리즘을 통해서 모두 구할 수 있음을 알 수 있다.

플로이드 워셜을 구현할 때, 중간 경유노드의 번호로 사용되는 K를 가장 바깥에 두고 3중 For문을 돌린다고 생각하면 편하다.

플로이드-워셜 O(N^3)

다익스트라는 불가능한가요?

전체 간선의 수 역시 작으므로 다익스트라를 N번 수행해도 무방할 것으로 보인다.

우선 순위 큐를 사용한 다익스트라 O((V+E)logV)에 N번을 곱해도, 해당 문제를 통과하기에는 충분할 것이다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static StringBuilder sb;
	static String[] splitedLine;
	final static int INF = 99999999;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		int N = Integer.parseInt(in.readLine());
		int M = Integer.parseInt(in.readLine());
		int[][] dp = new int[N][N];

		for (int i = 0; i < M; ++i) {
			splitedLine = in.readLine().split(" ");
			int src = Integer.parseInt(splitedLine[0]) - 1;
			int des = Integer.parseInt(splitedLine[1]) - 1;
			int weight = Integer.parseInt(splitedLine[2]);

			if (dp[src][des] == 0) {
				dp[src][des] = weight;
			} else if (dp[src][des] > weight) {
				dp[src][des] = weight;
			} else {

			}
		}

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (i != j && dp[i][j] == 0)
					dp[i][j] = INF;
			}
		}

		for (int k = 0; k < N; ++k) { // 경유
			for (int i = 0; i < N; ++i) { // 출발
				if (k == i) { // 출발지와 경유지가 같은 경우는 생략
					continue;
				}

				for (int j = 0; j < N; ++j) { // 도착
					if (k == j || i == j) { // 경유지와 도착지가 같거나, 출발지와 도착지가 같은 경우 생략
						continue;
					}

					// i->j로 가는것보다 i->k->j로 가는 경우가 더 빠른 경우, 최단거리 갱신
					if (dp[i][j] > dp[i][k] + dp[k][j]) {
						dp[i][j] = dp[i][k] + dp[k][j];
					}
				}
			}
		}

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if(dp[i][j]>=INF)
					sb.append("0 ");
				else
					sb.append(dp[i][j] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}