[백준 1719] 택배 (C++)

문제 링크: https://www.acmicpc.net/problem/1719

1719번: 택배

1. 주의할 점

- 다익스트라 알고리즘을 이용하면서 어떤 방식으로 경로표를 저장할 것인지 고려한다

 

2. 구현

- 모든 간선들의 정보를 V[] 벡터에 저장한다

- 1~Node까지 모든 Node를 시작점으로 하여 다익스트라 알고리즘을 수행하면서 경로표를 구할 수 있도록 한다

- 시작점에서 출발하는 겨우 tmp.start를 다음 Node로 설정하고, 이외의 경우에는 tmp.start를 cs로 갱신한다. 그리고 tmp.start를 Pre[다음 Node]에 저장한다

- 1~Node까지 Pre[] 배열의 값을 출력하며, Pre[]의 값이 -1인 경우에는 -만 출력한다

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct info {
	int idx, start;
	long long val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, s, e, val;
long long dist[201];
int pre[201];
vector<info> v[201];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
		tmp.idx = s;
		v[e].push_back(tmp);
	}
	for (int t = 1; t <= node; t++) {
		for (int i = 1; i <= node; i++) {
			dist[i] = MAX;
			pre[i] = 0;
		}
		dist[t] = 0;
		pre[t] = -1;
		priority_queue<info, vector<info>, cmp> pq;
		tmp.idx = t;
		tmp.val = 0;
		pq.push(tmp);
		while (!pq.empty()) {
			int cidx = pq.top().idx;
			int cv = pq.top().val;
			int cs = pq.top().start;
			pq.pop();
			if (dist[cidx] < cv) continue;
			for (int i = 0; i < v[cidx].size(); i++) {
				int next = v[cidx][i].idx;
				int nv = v[cidx][i].val;
				if (dist[next] > cv + nv) {
					if (cidx == t) {
						tmp.start = next;
						pre[next] = next;
					}
					else {
						tmp.start = cs;
						pre[next] = cs;
					}
					dist[next] = cv + nv;
					tmp.idx = next;
					tmp.val = cv + nv;					
					pq.push(tmp);
				}
			}
		}
		for (int i = 1; i <= node; i++) {
			if (pre[i] == -1) cout << '-' << " ";
			else cout << pre[i] << " ";
		}
		cout << endl;
	}
	system("pause");
	return 0;
}