글 읽기 - DP를 이용해 모든 최단 경로를 보기

pwr2011 4년 전 0

저희는 dist배열에다가 0~K개의 각각 갯수만큼의 경로를 지운 가장 최단 값들을 저장하는 형식으로 해서,

정답이 dist[N][K]가 되도록 했습니다, (K개의 경로를 없애서 갈수있는 최단거리를 저장한 배열값)

어떤게 문제일까요? 무조건 K개의 경로를 없앤게 정답이 아닌가요? 제출하자마자 바로 틀렸습니다가 나옵니다.

고수님들의 도움 부탁드립니다 ㅠㅠ

#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<functional>
using namespace std;
typedef pair<long long, long long> p;
const int MAX = 10000 + 1;
const int INF = 99'999'999'999;
int N, M, K;
vector<vector<p>> graph; // graph[i] = (destination, dist);
bool visit[MAX];
long long dist[MAX][21]; // dist[i][k] = minimum distance from s to i with delete k edges.
priority_queue<p, vector<p>, greater<p>> PQ;

long long dijkstra() {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= K; j++) dist[i][j] = INF;
	}
	visit[1] = 1;
	for (int k = 0; k <= K; k++)
		dist[1][k] = 0;
	for (int i = 0; i < graph[1].size(); i++) {
		long long next = graph[1][i].first;
		long long weight = graph[1][i].second;
		for (int k = 1; k <= K; k++)
			dist[next][k] = 0;
		dist[next][0] = weight;
		PQ.push(p(0, next));
	}

	while (!PQ.empty()) {
		long long here = PQ.top().second;
		PQ.pop();
		if (visit[here]) continue;
		visit[here] = true;
		for (int i = 0; i < graph[here].size(); i++) {
			long long next = graph[here][i].first;
			long long weight = graph[here][i].second;
			if (visit[next]) continue;
			long long ret = (dist[here][K] + weight < dist[here][K - 1]) ? dist[here][K] + weight : dist[here][K - 1];
			if (dist[next][K] > ret) {
				dist[next][K] = ret;
				PQ.push(p(ret, next));
			}
			if (dist[next][0] > dist[here][0] + weight) dist[next][0] = dist[here][0] + weight;
			for (int j = 1; j < K; j++) {
				ret = (dist[here][j] + weight < dist[here][j-1]) ? dist[here][j] + weight : dist[here][j - 1];
				if (dist[next][j] > ret) {
					dist[next][j] = ret;
				}
			}
		}
	}
	return dist[N][K];
}

int main() {
	cin >> N >> M >> K;
	
	graph.resize(N + 1);
	for (int i = 0; i < M; i++) {
		int s, d, w;
		cin >> s >> d >> w;
		graph[s].push_back(p(d, w));
		graph[d].push_back(p(s, w));
	}

	cout << dijkstra() << "\n";

	return 0;
}

lim551 4년 전 1

코드를 자세히 읽지는 않았는데 일단 INF 부터가 오버플로 나지 않나요?

pwr2011 4년 전 0

헉 그렇네요 일단 고치고 돌려봤는데 역시나 안되네요 ... ㅠㅠ

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

문제

문제

출처

ICPC

DP를 이용해 모든 최단 경로를 보기

pwr2011 4년 전 0

lim551 4년 전 1

pwr2011 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말