백준 1446 지름길 c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,d;
vector<pair<int,int> > vec[10001];
int v[10001];

void input() {
	cin >> n >> d;
	for(int i=0; i<n; i++) {
		int a,b,c;
		cin >> a >> b >> c;
		vec[a].push_back({b,c});
	}	
	
	for(int i=0; i<10001; i++) { v[i] = i; }
}

void solve() {
	for(int i=0; i<=d; i++) {
		if(i != 0) { v[i] = min(v[i],v[i-1] + 1); }
		for(int j=0; j<vec[i].size(); j++) { 
		    v[vec[i][j].first] = min({v[i] + vec[i][j].second,v[i] + (vec[i][j].first - i), v[vec[i][j].first]});
		}
	}
	
	cout << v[d];
}

int main() {	
	input();
	solve();
		
}

다익스트라 공부가 하고싶어져 백준 다익스트라 게시판에서 제일 쉬운걸로 찾아봤는데 다익스트라를 쓰는게 아니었다.

 

고속도로의 최대 길이가 10000 이고 지름길이 최대 12개 있기 때문에 완전탐색을 사용해도 O(10000*12) 밖에 안된다.

 

0부터 도착지점까지 지름길을 탔을때와 그냥 달렸을때를 비교해주면서 최소값을 갱신해주면 된다. 

 

 

**

c++ algorithm 헤더의 min 함수를 쓸때 인자 세개를 비교하려면 ({a,b,c}) 이런 식으로 중괄호로 묶어주면 된다!