글 읽기 - 소스에서 뭐가 문제인지 잘 못찾겠습니다.

sotter1020 5년 전 0

2번 예제에서 Poor KCM이 출력이 안되고 7이 출력되는데..

dist를 찍어봐도 어디를 고쳐야 할 지 모르겠습니다.

알려주시면 감사합니다 ㅠㅠ

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

const int INF = 1000 * 100 + 1;
vector<pair<pair<int, int>, int>> adj[101];
int N, M, K;
int TC;

vector<vector<int>> dijkstra(int src, int f) {
	vector<vector<int>> dist(N + 1, vector<int>(M + 1, INF));
	dist[src][0] = 0;
	priority_queue<pair<pair<int, int>, int>> pq;
	pq.push({ { 0, src }, 0 });
	while (!pq.empty()) {
		int cost = -pq.top().first.first;
		int here = pq.top().first.second;
		int fi = pq.top().second;
		pq.pop();
		if (dist[here][fi] < cost) continue;
		for (int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i].first.first;
			int nextDst = cost + adj[here][i].first.second;
			int fin = adj[here][i].second;

			if (fin + fi > f) continue;
			if (nextDst < dist[there][fin + fi]) {
				dist[there][fin + fi] = nextDst;
				pq.push({ { -nextDst, there }, fi + fin });
			}
		}
	}
	return dist;
}

int main() {
	cin >> TC;
	while (TC--) {
		cin >> N >> M >> K;
		while (K--) {
			int u, v, c, d;
			cin >> u >> v >> c >> d;
			adj[u].push_back({ {v,d},c });
		}
		vector<vector<int>> dist = dijkstra(1, M);
		int ret = INF;
		for (int i = 0; i < M + 1; ++i)
			ret = min(ret, dist[N][i]);
		if (ret == INF)
			cout << "Poor KCM" << endl;
		else
			cout << ret << endl;
	}
	return 0;
}

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

문제

문제

출처

ICPC

소스에서 뭐가 문제인지 잘 못찾겠습니다.

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말