글 읽기 - k번째 최단경로 찾기 ! 어떤 예외가 있는지 알려주실분..!

tpwls1213 5년 전 0

k번째 최단 경로를 찾으면 되니까

pq로 k번만 d배열에 접근하게 짰는데

90%에서 틀리네여 ㅠㅠ

혹시 어디가 틀린지 아시는분 알려주시면 감사하겠습니다~!

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int d[1111];
int cnt[1111];

int main() {
	memset(d, -1, sizeof(d));
	vector < vector<pair<int, int>>> graph;
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	graph.resize(n + 1);
	for (int i = 1; i <= n; i++) cnt[i] = k;
	for (int i = 0; i < m; i++) {
		int x, y, z; scanf("%d %d %d", &x, &y, &z);
		graph[x].push_back({ y,z });
	}

	priority_queue<pair<int, int>> pq;
	pq.push({ 0,1 });
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if ((d[here] == -1) || (d[here] != -1 && cnt[here] > 0)) {
			d[here] = cost;
			cnt[here]--;

			for (int i = 0; i < graph[here].size(); i++) {
				int next = graph[here][i].first;
				int ncost = -graph[here][i].second - cost;

				if (d[next] == -1 || (d[next] != -1 && cnt[next] > 0)) pq.push({ ncost,next });
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (d[1] == 0 && k != 1) d[1] = -1;
		printf("%d\n", d[i]);
	}
	return 0;
}

njchung99 5년 전 0

틀렸으니까 틀린거아닐까요? 호주가서 빡코딩하신다더니...;;

tpwls1213 5년 전 0

초심찾기프로젝트 2월4일에 시작합니다

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

문제

문제

출처

ICPC

k번째 최단경로 찾기 ! 어떤 예외가 있는지 알려주실분..!

tpwls1213 5년 전 0

njchung99 5년 전 0

tpwls1213 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말