[백준OJ] 1916번 최소비용 구하기

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

1916번: 최소비용 구하기

---

 

 

 

풀이

다익스트라를 이용해서 풀어주면 되겠다! 하고 풀었는데, 맞왜틀이라 왜지,,,,왜 시간초과가 나오지 하고 생각을 하다가 문제 조건에 시간제한이 0.5초라는것을 보았다. 그래서 우선순위큐를 이용한 다익스트라 알고리즘을 사용하여 풀었더니 바로 통과를 했다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define MAX	987654321
using namespace std;

vector<pair<int,int>> maze[1001];
int cost[1001];
bool visited[1001] = { 0 };
int n, m,st,en;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cost[i] = MAX;
	}
	for (int i = 0; i < m; i++) {
		int to, from, cost;
		cin >> to >> from >> cost;
		maze[to].push_back({ from,cost });
	}

	cin >> st >> en;
	priority_queue<pair<int,int>> pq;
	cost[st] = 0;
	pq.push({ 0,st });

	while (!pq.empty()) {
		int now = pq.top().second;
		int dist = -pq.top().first;
		pq.pop();

		if (cost[now] < dist) continue;

		for (auto next : maze[now]) {
			int next_node = next.first;
			int next_cost = next.second;

			if (cost[next_node] > next_cost + dist) {
				cost[next_node] = next_cost + dist;
				pq.push({ -(next_cost + dist),next_node });
			}
		}
	}

	cout << cost[en];
	
	return 0;
}