백준 14284 - 간선 이어가기 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14284

14284번: 간선 이어가기 2

다익스트라를 이용하는 문제입니다.

가중치가 주어졌을 때, 연결할 수 있는 최솟값을 출력하는 문제입니다.

연결했을 때의 최솟값만 출력하면 되기에 다익스트라 알고리즘을 이용해서 풀어주면 됩니다.

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#define INF 2100000000
#define F first
#define S second

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int Distance[5001];
int N, M, s, t;
vector<pair<int, int>> connect[5001];

void reset_distance(){
	for(int i = 1; i <= N; i++) Distance[i] = INF;
}

void dijstra(){
	Distance[s] = 0;
	q.push({Distance[s], s});
	while(!q.empty()){
		int x = q.top().S;
		int cost = q.top().F;
		q.pop();
		if(x == t) return;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = Distance[x] + connect[x][i].S;
			if(n_cost < Distance[xx]){
				Distance[xx] = n_cost;
				q.push({n_cost, xx});
			}
		}	
	}
}

void solve(){
	reset_distance();
	dijstra();
	cout << Distance[t];
}


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	cin >> s >> t;	
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.