백준 1916 - 최소비용 구하기(C++)

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

1916번: 최소비용 구하기

다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제였습니다.

다익스트라 알고리즘을 통해 시작점에서 출발하여 끝점까지의 최소 비용을 구하는 문제였습니다.

https://junseok.tistory.com/187

백준 1753 - 최단경로(C++)

해당 문제와 설명이 같으니 참고바랍니다.

 

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 210000000000

using namespace std;

priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> q;
int N, M;
int start, finish;
long long int Distance[1001];
bool check[1001];
vector<pair<int, int>> connect[1001];

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

void solve() {
	reset_Distance();
	memset(check, false, sizeof(check));
	Distance[start] = 0;
	q.push(make_pair(Distance[start], start));
	while (!q.empty()) {
		int x = q.top().second;
		int cost = q.top().first;
		q.pop();
		check[x] = true;
		if (x == finish) {
			cout << Distance[finish];
			break;
		}
		for (int i = 0; i < connect[x].size(); i++) {
			int xx = connect[x][i].first;
			int Cost = connect[x][i].second;
			if (!check[xx] && Distance[xx] > Distance[x] + Cost) {
				Distance[xx] = Distance[x] + Cost;
				q.push(make_pair(Distance[xx], xx));
			}
		}
	}
}

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(make_pair(y, cost));
	}
	cin >> start >> finish;
	solve();
	return 0;
}

 

 

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