백준 1446번 지름길 C++

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

 

D까지 가는 최소 거리를 구하는 문제이다. 역주행은 불가능하다. dp방식으로 해결하였다.

처음에는 거리를 지름길을 고려하지 않고 초기화해주고 지름길들의 도착 위치를 기준으로 정렬한 뒤, 도착 전의 위치들을 검사하면서 도착 위치까지의 최소 거리를 찾아서 지름길을 이용한 최소 거리들을 구하고, 마지막에는 처음부터 D까지 검사하면서 최소 거리를 찾는 방식으로 문제를 해결하였다.

 

풀고 나서 시작 위치를 기준으로 정렬해도 맞았는데, 이유는 잘 모르겠다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int dist_min[10001];

struct distInfo{
	distInfo(int start, int end, int dist) :start(start), end(end), dist(dist) {};
	int start;
	int end;
	int dist;
};

bool compare1(distInfo lhs, distInfo rhs) {
	return lhs.end < rhs.end;
}
bool compare2(distInfo lhs, distInfo rhs) {
	return lhs.start < rhs.start;
}

vector<distInfo> v;
int n, d;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i <= 10000; i++) {
		dist_min[i] = i;
	}

	cin >> n >> d;
	for (int i = 0; i < n; i++) {
		int start, end, dist;
		cin >> start >> end >> dist;
		v.push_back({ start,end,dist });
	}

	sort(v.begin(), v.end(), compare1);
	for (auto a : v) {
		for (int i = 0; i <= a.start; i++) {
			dist_min[a.start] = min(dist_min[a.start], dist_min[i] + a.start - i);
		}
		dist_min[a.end] = min(dist_min[a.end], dist_min[a.start] + a.dist);
	}


	for (int i = 0; i <= d; i++) {
		dist_min[d] = min(dist_min[d], dist_min[i] + d - i);
	}
	cout << dist_min[d];
};