백준 Gold 2 플로이드 2

플로이드 2 (백준 Gold 2)

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

n개의 도시와 m개의 도시에 도착하는 버스가 있다

• 각각의 버스는 시작 도시, 도착 도시, 비용이 존재
  

모든 쌍 (A,B)에 대하여
A->B의 최소 비용을 출력하고
그 경로를 출력하는 문제

• 다만 도착할 수 없다면 0 출력
  

풀이 방법

이전에 보았던 플로이드-워셜 문제와 유사하다

유의사항

• 각각의 버스는 ‘단방향’!
  또한 비용만 다른 중복 경로 존재하므로
  최단 경로만을 받아서 정리
  

풀이법

• maps[i][j].first : i->j로 최단거리로 가기 위해 방문해야 하는 경로 저장
  (이전에 풀었던 것도 사실 i->j를 방문하기 위해 방문해야 하는 것)
  

• 그렇다면 maps[i][j].first를 next라 칭했을때
  maps[next][j].first 를 타고 가는 방식으로
  i->j 의 경로를 구할 수 있다!
  (반대로 next가 ‘제자리’에서 돈다면 찾을수 없다는 반증)
  

• 그렇기에
  해당 경로를 ‘방문’하면서 목적지에 도달하는지를 체크하는 함수를 만들어
  경로를 반환하였다
  

제출 코드

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

using namespace std;

typedef pair<int, int> pii;

vector<int> getPath(vector<vector<pii>>& maps, int start, int end)
{
	vector<int> result;
	result.push_back(start);

	int next = maps[start][end].first;

	bool bFind = true;

	while (next != end)
	{
		result.push_back(next);

		if (next == maps[next][end].first)
		{
			bFind = false;
			break;
		}
		next = maps[next][end].first;
	}

	result.push_back(end);

	if (bFind == false)
		result.clear();

	return result;
}

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;
		maps[i][i].second = 0;
	}

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

		if (maps[a][b].second > c)
		{
			maps[a][b].first = b;
			maps[a][b].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 (maps[i][j].second == vv)
			{
				cout << 0 << ' ';
			}
			else
			{
				cout << maps[i][j].second << ' ';
			}
		}
		cout << '\n';
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
			{
				cout << 0 << '\n';
				continue;
			}

			vector<int> r = getPath(maps, i, j);

			cout << r.size() << ' ';
			for (int p : r)
			{
				cout << p << ' ';
			}
			cout << '\n';
		}
	}

	return 0;
}

결과

처음에는 first에 다른 조건을 넣어야 할지
고민했으나 이전의 방식을 응용하면 풀 수 있단걸 알았다