[7주차] 백준 11780번: 플로이드2_C++

백준 11780: 플로이드2

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

11780번: 플로이드 2

---

- 도시의 개수 n을 입력한다

- 버스의 개수 m을 입력한다

- 버스의 정보를 주어진다.

// '버스의 시작도시 도착 도시 필요한 비용'으로 이루어져 있음
- 도시에서 도시로 가는 경우에 필요한 최소 경로에 지나쳐야 하는 도시의 개수 와 도시의 경로를 출력해준다 

// 만약 갈 수 없는 경우에는 0을 출력한다

// 즉, 도시 1-> 도시 2의 정보, 도시2 -> 도시3의 정보 등..을 출력해주는 것이다

---

대체 문제가 뭘 말하는건지 모르겠어서 한참봤다,,,,

문제를 이해하고 정리하고 나서도 생각을 오래 해보니 쉬워보여서 이것저것 해보려고 하니까 잘 못하겠었다...

그래서 구글링해보니까 이건 알고리즘 최단경로 역추적 문제라고 한다. 정리하고 넘어가야할 것 같다

---

[참고] https://codenme.tistory.com/6?category=1026697

---

[코드참고] https://codenme.tistory.com/9

#include<iostream>
#include<vector>
using namespace std;
int arr[101][101];
const int inf = 987654321;


int nxt[101][101];
int main() {
	int n, m, a, b, c;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			arr[i][j] = inf;
		arr[i][i] = 0;
	}
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (arr[a][b]>c) {//중요!
			arr[a][b] = c;
			nxt[a][b] = b;
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int use = arr[i][k] + arr[k][j];
				if (arr[i][j] > use) {
					arr[i][j] = use;
					nxt[i][j] = nxt[i][k];
				}

			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != inf)
				cout << arr[i][j] << " ";
			else
				cout << 0 << " ";
		}
		cout << endl;
	}
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] == inf||arr[i][j]==0)
				cout << "0" << endl;
			else {
				//***아래부터 경로 추적
				vector<int> path;
				path.push_back(i);
				while (path.back() != j) {
					int now = path.back();
					path.push_back(nxt[now][j]);
				}
				cout << path.size() << " ";
				for (auto p : path)
					cout << p << " ";
				cout << endl;

			}
		}
	}
	


}