7) 백준 1916 - 최소비용 구하기

1916번: 최소비용 구하기 (acmicpc.net)

1916번: 최소비용 구하기

---

다익스트라 사용한 문제.

계속 틀려서 고민하다가 어이없게 맞춘 문제인데 어떤 차이가 있는지 모르겠다.

#include <bits/stdc++.h>

using namespace std;

int cost[1001];
int dij[1001];

int main(void) {
	fill_n(cost, 1001, 100000001);
	fill_n(dij, 1001, 100001);
	
	// dij : arrive point, cost
	vector<vector<pair<int, int>> > dij(1001);
	
	int N, M, start, end, a, b, w;
	cin >> N;
	cin >> M;
	for(int i = 0; i < M; i++) {
		cin >> a >> b >> w;
		for(int j = 0; j < dij[a].size(); j++) {
			if(dij[a][j].first == b && dij[a][j].second > w) {
				dij[a][j].second = w;
				break;
			}
		}
		dij[a].push_back(make_pair(b, w));
	}
	cin >> start >> end;
	
	cost[start] = 0;
	// Queue : -cost, vertex_No
	priority_queue<pair<int, int> > q;
	q.push(make_pair(-cost[start], start));
		
	while(!q.empty()) {
		int start_point_cost = -q.top().first;
		int start_point = q.top().second;
        
/*		왜 틀렸는지 모르겠는 구간
		if(start_point == end) {
			break;
		}
*/

		for(int i = 0; i < dij[start_point].size(); i++) {
			// cost[도착지점] > cost[출발지점] + weight 
			if(cost[dij[start_point][i].first] > cost[start_point] + dij[start_point][i].second) {
				cost[dij[start_point][i].first] = cost[start_point] + dij[start_point][i].second;
				q.push(make_pair(-cost[dij[start_point][i].first], dij[start_point][i].first));
			}
		}
		q.pop();
	}
	
	cout << cost[end] << endl;
	
	return 0;	
}

원래 계획은 다익스트라의 특징으로 최소 거리가 구해졌을경우 다시는 방문하지 않기에 if문을 걸어서 조금더 빠르게 하려던 계획이었다.

 

저 if문을 사용하고 while문 마지막의 q.pop()을 그 위에 사용하면 또 된다..

무슨 차이지...

---

아 바보였다....

얘는 priority_queue였지....

으이구 인간아 ᕙ( ︡’︡益’︠)ง