(백준/c++) 1238 - 파티 / 최단경로그래프, 플로이드 워샬

 

"(백준/c++) 1238 - 파티 / 최단경로그래프, 플로이드 워샬"

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

---

 

🏆 solved.ac 난이도: 골드3 

🔸 문제 핵심 

• 단방향 도로
• 갔다가 돌아오는 최단경로 

 

🔹 주요 코드 부분

• 파란줄: form ~ stopper 시작점부터 경유지까지 무한이면, 연결되어 있지 않는다는 뜻이기 때문에 무시해주자.
• 노란줄: 시작점부터 도착점 > 시작점부터 경유지 + 경유지부터 도착점이 구조를 외우지 말고 완화(relax)를 이해하자. 

#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

//vector<pair<int, int>> students[1'001]; 
int students[1'001][1'001];
int result[1'001];
int main(void)
{
	int n, m, x; 
	cin >> n >> m >> x;
	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			students[i][j] = 10'000'001; 
			if (i == j)
			{
				students[i][j] = 0; 
			}
		}
	}

	for (int i = 0; i < m; ++i)
	{
		int a, b, t;
		cin >> a >> b >> t; 
		
		students[a][b] = t;
		//students[a].push_back(make_pair(b, t));
	}

	for (int stopover = 1; stopover <= n; ++stopover)
	{
		for (int form = 1; form <= n; ++form)
		{
            if (students[form][stopover] == 10'000'001)
				continue;
			for (int to = 1; to <= n; ++to)
			{
				if (students[form][to] > students[form][stopover] + students[stopover][to])
				{
					students[form][to] = students[form][stopover] + students[stopover][to];
				}
			}
		}
	}

	int result = 0;
	for (int i = 1; i <=n; ++i)
	{
		if ((result < students[x][i] /*x->i*/ + students[i][x]) && i!=x)
		{
			result = students[x][i] /*x->i*/ + students[i][x];
		}
	}
	
	cout << result;
	return 0;

}