백준 1719 c++ "택배" -[PlusUltraCode]

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

 

 

 

 

 

[필자 사고]

다익스트라 혹은 폴로이드 워셜을 이용하여 푸는 문제이다.

필자는 다익스트라를 이용하여 문제를 해결 하였다.

다른 문제와 달리 이 문제의 핵심 포인트는 지나간 경로중 가장 첫번째 경로를 저장해야 된다.

필자는 Union과 find를 이용하여 집합을 이용해 풀었다.

먼저 parent배열에 부모노드를 저장해 주었다. 

다익스트라 알고리즘이 끝난 후 parent 배열을 Union 해주어 쉽게 처음 시작한 노드를 찾을 수 있었다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include<cstring>
#include <string>
using namespace std;

typedef pair<int, int> Node;

vector<vector<Node>> Arr;
vector<vector<int>> pathLoad;
vector<bool> visited;
vector<int> parent;

int find(int a) {
	if (a == parent[a]) {
		return a;
	}
	return parent[a] = find(parent[a]);
}

void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		parent[b] = a;
	}
}




int N, M;

void Dijkstra(int start) {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,start });
	pathLoad[start][start] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		int ac_Cost = pq.top().first;
		pq.pop();
		if (visited[nowIdx])continue;
		visited[nowIdx] = true;

		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;
			if (pathLoad[start][nextIdx] > pathLoad[start][nowIdx] + nextCost) {
				
				if (ac_Cost != 0) {
					parent[nextIdx] = nowIdx;
				}
			
				pathLoad[start][nextIdx] = pathLoad[start][nowIdx] + nextCost;
				pq.push({ pathLoad[start][nextIdx],nextIdx });
				

			}
		}
	}
}

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	pathLoad.resize(N + 1);
	visited.resize(N + 1, false);
	
	for (int i = 0; i <= N; i++) {
		pathLoad[i].resize(N + 1, INT_MAX);
	
	}

	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s].push_back({ w,e });
		Arr[e].push_back({ w,s });

	}


}

void Init() {
	parent.clear();
	parent.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		parent[i] = i;
	}
	visited.clear();
	visited.resize(N + 1, false);
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	for (int i = 1; i <= N; i++) {
		Init();
		Dijkstra(i);
		for (int k = 1; k <= N; k++) {
			if (pathLoad[i][k] == 0||pathLoad[i][k]==INT_MAX) {
				parent[k] = -1;
			}


		}

		for (int k = N; k >=1; k--) {
			if (k == i)continue;
			Union(parent[k], k);
		}


		for (int k = 1; k <= N; k++) {
			if (parent[k] == -1) {
				cout << "- ";
			}
			else {
				int a=find(parent[k]);
				cout << parent[k] << " ";
			}
		}
		cout << '\n';
	}
	
}