[C++] 백준 1719 : 택배

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

1719번: 택배

백준 1719번 택배 문제를 풀었다.

 

간선의 가중치가 양수이고 최단 경로를 찾는 문제라서 다익스트라를 사용했다.

 

path 배열은 다익스트라를 수행할 때 이전 노드를 저장하는 배열이다.

예를 들어 1번 노드에서 다익스트라를 수행하면 path배열은 아래와 같이 저장된다.

index	1	2	3	4	5	6
value	0	1	1	3	2	5

이 path 배열을 다르게 보면, index 노드로부터 1번 노드로 가기 위해 가장 먼저 가야할 노드를 저장하고 있는 것을 확인할 수 있다.

6->1 로 가기 위해 가장 먼저 가야할 노드는 5

5->1 로 가기 위해 가장 먼저 가야할 노드는 2

4->1 로 가기 위해 가장 먼저 가야할 노드는 3

3->1 로 가기 위해 가장 먼저 가야할 노드는 1

2->1 로 가기 위해 가장 먼저 가야할 노드는 1

1->1 은 0이니까 '-'

 

결국 다익스트라를 한 번 수행하면 문제에서 요구하는 정답 중 한 개의 열이 완성되는 것이다.

그래서 n번 다익스트라를 수행한 후 ans 배열을 채워서 출력해주면 정답이다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

#define INF 1000000000

struct Node {
	int end;
	int cost;
	Node(){}
	Node(int x, int y) :end(x), cost(y) {}
};

struct compare {
	bool operator()(Node a, Node b) {
		return a.cost > b.cost;
	}
};

int n, m;
vector<Node> v[201];
priority_queue<Node, vector<Node>, compare> pq;
vector<int> dist;
vector<int> path;
int ans[201][201];

void Dijkstra(int start) {
	dist.assign(201, INF);
	path.assign(201, 0);
	dist[start] = 0;
	pq.push(Node(start, dist[start]));

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		int cost = temp.cost;
		pq.pop();

		if (dist[cur] < cost)
			continue;

		for (int i = 0; i < v[cur].size(); i++) {
			temp = v[cur][i];
			int next = temp.end;
			int next_cost = cost + temp.cost;
			if (dist[next] > next_cost) {
				dist[next] = next_cost;
				pq.push(Node(next, next_cost));

				path[next] = cur;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		ans[i][start] = path[i];
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		v[start].push_back(Node(end, cost));
		v[end].push_back(Node(start, cost));
	}

	for (int i = 1; i <= n; i++) {
		Dijkstra(i);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (ans[i][j] == 0)
				cout << '-' << ' ';
			else
				cout << ans[i][j] << ' ';
		}
		cout << "\n";
	}

	return 0;
}