백준 5972 - 택배 배송(C++)

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

5972번: 택배 배송

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

정점 1번에서 시작해서 N번까지 가는게 필요한 최소 비용을 구하는 문제입니다.

간선의 가중치가 1만 있는 것이 아니기에 다익스트라 알고리즘을 통해서 최단 거리를 구해야하는 문제였습니다.

 

다익스트라 알고리즘이 궁금하다면 해당 링크를 통해 확인하시면 됩니다.

https://junseok.tistory.com/187

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

 

 

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

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

using namespace std;

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
int N, M;
vector<pair<int, int>> line[500001];
long long Distance[500001];

void Dijstra() {
	Distance[1] = 0;
	q.push({ 0,1 });
	while (!q.empty()) {
		int x = q.top().second;
		long long cost = q.top().first;
		q.pop();
		for (int i = 0; i < line[x].size(); i++) {
			int xx = line[x][i].first;
			int Cost = line[x][i].second;
			if (Distance[xx] > Distance[x] + Cost) {
				Distance[xx] = Distance[x] + Cost;
				q.push({ Distance[xx], xx });
			}
		}
	}
}

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

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;
		line[x].push_back({ y,cost });
		line[y].push_back({ x,cost });
	}
	solve();
	return 0;
}

 

 

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