백준 5972 c++ "택배 배송" -[PlusUltraCode]

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

5972번: 택배 배송

 

[필자 사고]

 

문제는 복잡해 보이지만 전형적인 다익스트라 알고리즘을 이용한 최단거리 문제이다

 

이 부분만 잘 캐치한다면 쉽게 문제를 해결할 수 있을 것이다.

 

[소스 코드]

 

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

typedef pair<int, int> Node;

int N, M;

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

void Dijkstra() {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,1 });
	pathLoad[1] = 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[nextIdx] > pathLoad[nowIdx] + nextCost) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextCost;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}
}

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	pathLoad.resize(N + 1, INT_MAX);
	visited.resize(N + 1, false);
	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 });

	}
}

int main(void) {
	Input();
	Dijkstra();
	cout << pathLoad[N];
}