글 읽기 - 맞았지만 이전 코드가 틀린 이유를 모르겠습니다....

thoon916 2년 전 1

도로를 포장을 최대로 많이 한 것이 당연히 시간이 줄어드는 것으로 생각하고 간단히 N번까지 가는데에 도로 포장을 최대로 많이 한 것을 출력했을때는 86%에서 틀렸습니다가 나오고 반복문을 이용해 도로 포장을 1번에서 K번까지 한 값의 최솟값을 answer에 저장하여 출력하게 되면 맞습니다.

혹시 이 둘의 차이가 뭘까요...??

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define INF 100000000000

using namespace std;

int N, M, K;

priority_queue < tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
vector<vector<pair<int, int>>> city;
vector<vector<long long>> dist;

void doDijkstra()
{
	dist.resize(N + 1, vector<long long>(K + 1, INF));

	pq.push({ 0,1,0 });

	while (!pq.empty())
	{
		long long cur_dist = get<0>(pq.top());
		int cur_idx = get<1>(pq.top());
		int cur_cnt = get<2>(pq.top());

		pq.pop();
		if (dist[cur_idx][cur_cnt]<cur_dist) continue;

		for (auto temp : city[cur_idx])
		{
			
			if (dist[temp.first][cur_cnt] > temp.second + cur_dist)
			{
				dist[temp.first][cur_cnt] = temp.second + cur_dist;
				pq.push({ dist[temp.first][cur_cnt],temp.first,cur_cnt});
			}
			if (cur_cnt<K && dist[temp.first][cur_cnt + 1] > cur_dist)
			{
				dist[temp.first][cur_cnt + 1] = cur_dist;
				pq.push({ dist[temp.first][cur_cnt + 1],temp.first,cur_cnt + 1 });
			}
		}

	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;
	city.resize(N + 1);
	for (int i = 0; i < M; i++)
	{
		int from, to, weight;
		cin >> from >> to >> weight;
		city[from].push_back({ to,weight });
		city[to].push_back({ from,weight });
	}

	doDijkstra();

    // 맞은 코드
	long long answer = INF;
	for (int i = 0; i <= K; i++)
	{
		if (answer > dist[N][i]) answer = dist[N][i];
	}

	cout << answer;
    
    // 86%에서 틀린 코드
    //cout << dist[N][K];
}

playsworld16 2년 전 6

N번까지 가는데 최대로 포장할 수 있는 도로의 개수가 K보다 작을 수 있습니다.

반례 드립니다.

사실 #2 의 경우 K값을 5로 바꾸면 정답을 출력합니다.

이는 같은 도로를 여러번 사용하여 5번째에 N번으로 도달하는 경로가 존재하기 때문입니다.

정리하자면

1. N번까지 가는데 최대로 포장할 수 있는 도로의 개수가 K보다 작고,

2. K개의 도로를 사용하여 N번으로 도달하는 경로가 존재하지 않는 경우에

오답을 출력합니다.

thoon916 2년 전 1

아 감사합니다 ㅎㅎ

K보다 작은 횟수로 도착하게 되면 dist[N][K]가 초기화된 값(INF)로 나올 수 있네요

덕분에 깔끔하게 이해했습니다.

uhmtoto 1년 전 1

저도 같은 이유로 고민했었는데 명쾌하게 해결됐네요

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

맞았지만 이전 코드가 틀린 이유를 모르겠습니다....

thoon916 2년 전 1

playsworld16 2년 전 6

thoon916 2년 전 1

uhmtoto 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말