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

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

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

틀린 풀이

• 플로이드-와샬 알고리즘을 사용한 풀이
• 11%에서 시간 초과

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_COST = 100000;

int N;

//dist[a][b] = a에서 b로 갈 수 있는 최소 비용
int dist[1001][1001];

//플로이드-와샬 알고리즘
void floyd() {
	for (int i = 0; i < N; ++i) {
		dist[i][i] = 0;
	}

	//i지점 -> j지점으로 이동할 때 거쳐가는 지점 K
	for (int k = 0; k < N; ++k)
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < N; ++j)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

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

	cin >> N;

	//adj, dist 초기화
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			dist[i][j] = MAX_COST;
		}
	}

	//버스 비용 입력받기
	int M;
	cin >> M;
	for (int i = 0; i < M; ++i) {
		int start, end, cost;
		cin >> start >> end >> cost;

		dist[start - 1][end - 1] = min(cost, dist[start - 1][end - 1]);
	}

	floyd();

	//출발지점, 도착지점 입력받기
	int A, B;
	cin >> A >> B;
	cout << dist[A - 1][B - 1];

	return 0;
}

풀이

• 다익스트라 알고리즘을 사용한 풀이

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

typedef long long ll;

const ll MAX_COST = 100000000;

int N;

//start지점에서 각 지점까지의 최소 비용
vector<ll> dist(1000, MAX_COST);

//adj[curNode] = {{nextNode, w}, ...}
vector<vector<pair<int, ll>>> adj(1000, vector<pair<int, ll>>());

void priority_queue_dijkstra(int start) {

	priority_queue<pair<ll, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;

	while (!pq.empty()) {
		ll curW = -pq.top().first;
		int curNode = pq.top().second;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			ll nextW = adj[curNode][i].second;

			if (dist[nextNode] > curW + nextW) {
				dist[nextNode] = curW + nextW;
				pq.push({ -dist[nextNode], nextNode });
			}
		}
	}
}

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

	cin >> N;

	//버스 비용 입력받기
	int M;
	cin >> M;
	for (int i = 0; i < M; ++i) {
		int start, end;
		ll cost;
		cin >> start >> end >> cost;

		start--;
		end--;

		//중복된 경로의 버스 있는지 검사
		bool replaced = false;
		for (int i = 0; i < adj[start].size(); ++i) {
			if (adj[start][i].first == end) {
				adj[start][i].second = min(cost, adj[start][i].second);
				replaced = true;
				break;
			}
		}
		if (!replaced) {
			adj[start].push_back({ end, cost });
		}
	}

	
	//출발지점, 도착지점 입력받기
	int A, B;
	cin >> A >> B;

	A--; B--;

	priority_queue_dijkstra(A);
	cout << dist[B];

	return 0;
}

📌참고자료

• 그래프 최단거리 알고리즘 (다익스트라, 벨만-포드, 플로이드-와샬)
  [TIL] 22-01-03