백준 Gold 3 택배

택배 (백준 Gold 3)

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

n개의 집하장과 m개의 경로가 아래와 같이 주어진다

이러한 경로들을 받아

다음과 같이 ‘최단 경로’로 ‘이동’시키기 위해
‘가장 먼저 거쳐야 하는 집하장’을 기록하는 문제

풀이 방법

문제 자체는 ‘플로이드-워셜’을 사용하여 풀 수 있으나
다소 응용이 필요하다

• n~m의 각 요소에 대한 최단거리를 구함
  
• 최단거리를 구할 때, ‘가장 먼저’ 거쳐야 하는 집하장을 표기
  

상세 풀이

1. pair<int,int>를 통해 ‘첫 경로’와 ‘총 비용’을 별도로 관리
   
2. i == j라면 자기 자신을, 경로가 연결되었다면 [i][j] = j, [j][i] = i로 초기화
   
3. 플로이드-워셜을 진행하며, k번째 요소를 경유하는게 더 짧다면 k번째의 ‘첫 경로’를 따라가도록 설정
   

제출 코드

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

typedef pair<int, int> pii;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	const int vv = 1e9;

	vector<vector<pii>> maps(n + 1, vector<pii>(n + 1, { 0,vv }));

	for (int i = 0; i <= n; i++)
		maps[i][i].first = i;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		maps[a][b].first = b;
		maps[a][b].second = c;
		maps[b][a].first = a;
		maps[b][a].second = c;
	}

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (maps[i][j].second > maps[i][k].second + maps[k][j].second)
				{
					maps[i][j].first = maps[i][k].first;

					maps[i][j].second = maps[i][k].second + maps[k][j].second;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
			{
				cout << "- ";
				continue;
			}

			cout << maps[i][j].first << ' ';
		}

		cout << '\n';
	}

	return 0;
}

결과

플로이드 워셜의 응용 문제로
처음에는 first 부분에 k를 그대로 대입하였다가
예제에서 틀렸다

이후, ‘경로’의 ‘요소’를 따라가는 쪽으로 수정하여 통과