1956 ์šด๋™

์•Œ๊ณ ๋ฆฌ์ฆ˜(ํ”Œ๋กœ์ด๋“œ ์›Œ์…œ)

1. ๋ฌธ์ œ ํŒŒ์•… : ๊ทธ๋ž˜ํ”„ ์ƒ์˜ ์–ด๋–ค ์ ๋“ค ์ง‘ํ•ฉ์ด๊ฑด ์ตœ์†Œ๋กœ ์‚ฌ์ดํด์„ ์ด๋ฃจ๋Š” ์ง‘ํ•ฉ์ด๋ฉด ๋จ
2. ๊ทธ๋ž˜ํ”„ ๊ด€๋ จ ์•Œ๊ณ ๋ฆฌ์ฆ˜
	1. ๋‹ค์ต์ŠคํŠธ๋ผ : ์ถœ๋ฐœ์ ์—์„œ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ -> ํ•ด๋‹น x
	2. ๋ฐธ๋งŒํฌ๋“œ : ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๋งˆ์ฐฌ๊ฐ€์ง€
	3. MST : ์ตœ์†Œ์‹ ์žฅํŠธ๋ฆฌ -> ์‚ฌ์ดํด์€ ๊ฐ์ง€ํ•  ์ˆ˜ ์žˆ์œผ๋‚˜, ๊ทธ๊ฒƒ์ด ์ตœ์†Œ ์‚ฌ์ดํด์ธ์ง€ ๋ชจ๋ฆ„ and ์‚ฌ์ดํด๋งŒ์„ ์ถ”์ถœํ•ด๋‚ด๊ธฐ ์–ด๋ ค์›€
	4. ํ”Œ๋กœ์ด๋“œ ์›Œ์…œ : ๋ชจ๋“  ์ •์  ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ
		-> ์ž๊ธฐ ์ž์‹ ์€ ์›๋ž˜ 0์œผ๋กœ ํ‘œ์‹œํ•˜์ง€๋งŒ, ์ด ๋ฌธ์ œ์—์„  INF๋กœ ํ•œ๋‹ค๋ฉด ์‚ฌ์ดํด์„ ๊ฐ์ง€ํ•  ์ˆ˜ ์žˆ๊ณ  ๋˜ ์ตœ์†Œ ์‚ฌ์ดํด๋„ ๊ฐ์ง€ํ•˜๊ธฐ ์‰ฌ์›€

์ฝ”๋“œ

#include <bits/stdc++.h>
#define INF 2000000000
 
using namespace std;
 
long long N, E, edges[401][401];
 
int floid();
 
int main() {
	cin >> N >> E;
	for (int i = 0; i < 401; i++)
		for (int j = 0; j < 401; j++)
			edges[i][j] = INF;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges[a][b] = c;
	}
 
	cout << floid();
}
 
int floid() {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				if (edges[j][k] > edges[j][i] + edges[i][k])
					edges[j][k] = edges[j][i] + edges[i][k];
 
	int result = INF;
	for (int i = 1; i <= N; i++)
		result = result < edges[i][i] ? result : edges[i][i];
 
	if (result == INF)
		return -1;
	return result;
}