백준 1446 c++ "지름길" -[PlusUltraCode]

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

 

 

 

[필자 사고]

다익스트라 알고리즘을 알고 있다면 쉽게 문제를 해결할 수 있다.

 

이 문제의 특잉한 점은 모든 index+1 을 그래프로 연결해줘야 된다는 점이다.

 

또한 도착지점이 D보다 넘어가면 문제가 생기므로 이 또한 주의 해야 된다.

 

[소스 코드]

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

typedef pair<int, int> Node;

int N, D;

vector<vector<Node>> Arr;

vector<int> pathLoad;

void Dijkstra() {
	priority_queue<Node, vector<Node>,greater<Node>> pq;
	pq.push({ 0,0 });
	pathLoad[0] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		
		if (nowIdx == D) {
			cout << pq.top().first;
			return;
		}
		pq.pop();
		
		
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;
			if (nextIdx<=D&&nextIdx>=0&&
				pathLoad[nextIdx] > pathLoad[nowIdx] + nextCost) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextCost;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}
}

void Input() {
	cin >> N >> D;
	Arr.resize(D + 1);
	
	pathLoad.resize(D + 1, INT_MAX);
	for (int i = 0; i < D; i++) {
		Arr[i].push_back({ 1,i + 1 });
	}
	for (int i = 0; i < N; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		if (e > D || s > D)continue;
		Arr[s].push_back({ w,e });

	}
}



int main(void) {
	Input();
	Dijkstra();
}