백준 20007 - 떡 돌리기(C++)

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

20007번: 떡 돌리기

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

Y점에서 0~N번 점까지 떡을 돌리려고 합니다.
떡은 한개만 들고 다닐 수 있기 때문에 어느 곳을 가든 항상 왕복을 해야합니다. -> 다익스트라를 통해 거리를 구한 뒤, *2를 하면 됩니다.
거리가 가장 짧은 곳부터 오름차순으로 방문하기 때문에 거리를 구한 뒤, 정렬을 해주면 됩니다.

거리의 합이 X 이하만 된다면 몇 곳이든 들릴 수 있기 때문에, 이를 확인해주며,
잠은 항상 집에서 자야하기에, 왕복거리가 X보다 크게 된다면 떡을 돌릴 수 없게 됩니다.


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

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 98765432100
#define LL long long
#define F first
#define S second

using namespace std;

int N, M, X, Y;
vector<pair<int, int>> connect[1001];
LL Distance[1001];
priority_queue<pair<LL, int>, vector<pair<LL, int>>> q;

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

void Dijstra(int st){
	reset_distance();
	Distance[st] = 0;
	q.push({-0, st});
	while(!q.empty()){
		int x = q.top().S;
		LL cost = -q.top().F;
		q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = cost + connect[x][i].S;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void check_day(){
	int Day = 0;
	LL sum = 0;
	for(int i = 0; i < N; i++){
		if(sum + Distance[i] > X){
			Day++;
			sum = Distance[i];
		}
		else sum += Distance[i];
	}
	if(sum > 0) Day++;
	cout << Day;
}

void solve(){
	bool can = true;
	Dijstra(Y);
	for(int i = 0; i < N; i++){
		Distance[i] *= 2; //왕복임으로 *2
		if(Distance[i] > X) can = false;
	}
	sort(Distance, Distance+N);
	if(can) check_day();
	else cout << "-1";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> X >> Y;
	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});
	}	
	solve();
	return 0;
}

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