티스토리 뷰

백준

백준 소스코드 [C++] 5972 택배 배송

Hani_Levenshtein 2020. 8. 27. 00:32

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

 

5972번: 택배 배송

문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현��

www.acmicpc.net

백준 소스코드 [C++] 5972 택배 배송

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
using namespace std;
int v, e, start,desti, s, d, weight;
vector <pair<int, int>> adj[50000];
vector<int> dijkstra(int src) {
	priority_queue <pair<int, int> > pq;
	vector<int> dist(v, INT_MAX);
	dist[src] = 0;
	pq.push({ 0,src });
	while (pq.empty() != true) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (dist[here] < cost) continue;
		for (int i = 0;i < (int)adj[here].size();i++) {
			int there = adj[here][i].first;
			int nextdist = cost + adj[here][i].second;
			if (dist[there] > nextdist) {
				dist[there] = nextdist;
				pq.push({ -nextdist,there });
			}
		}
	}
	return dist;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> v>> e;
	for (int i = 0;i < e;i++) {
		cin >> s >> d >> weight;
		adj[s-1].push_back(make_pair(d-1, weight));
		adj[d - 1].push_back(make_pair(s - 1, weight));
	}

	cout << dijkstra(0)[v - 1];
	return 0;
}
댓글