글 읽기 - 어떤 케이스에서 오류가 나는지를 모르겠네요..

ljjk159 5년 전 0

코드가 길어서 죄송합니다 ㅠㅠ

우선순위 큐를 이용한 다익스트라 알고리즘으로 문제를 해결하려고 했는데

~~81%까지 진행되고~~ 틀렸다고 나오네요..

그래서 90~92번째 줄을 넣고 채점해보니 런타임 에러가 나오는 걸로 봐서

중복된 엣지가 들어간 것 같지는 않고

엣지가 덜 들어가서 문제가 되는 것 같은데.. (문제에서 모든 컴퓨터 간 연결이 되어 있다고 했으므로, 답은 스패닝 트리가 될 것이라 생각하고 풀었습니다.)

어떤 케이스에서 문제가 되는건지를 도저히 모르겠습니다..

참고로, 다익스트라 알고리즘을 통한 탐색에서 vertex가 갱신될 때마다 이전 vertex와 새로운 vertex를 잇는 edge를 추가하는 식으로 알고리즘을 짰습니다.

(selectedEdge에 이 edge들을 저장했습니다.)

고수분들 도와주시면 정말 감사하겠습니다!!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <functional>
using namespace std;

#define INF 0x7fffffff
class graph {
private:
	int num;
	vector<vector<pair<int, int>>> adj;
	vector<int> cost;
	vector<bool> visit;
	struct compare {
		bool operator() (const vector<int> &a, const vector<int> &b) {
			return a[2] > b[2];
		}
	};

public:
	vector<pair<int, int>> selectedEdge;
	void init(int v) {
		num = v;
		adj.resize(v);
		for (int i = 0; i < v; i++)
			adj[i].resize(0);
		cost.resize(v);
		visit.resize(v);
	}

	void addEdge(int u, int v, int c, bool directed = false) {
		adj[u].push_back(make_pair(v, c));
		if (!directed)
			adj[v].push_back(make_pair(u, c));
	}

	void dijkstra(int s) {
		priority_queue<vector<int>, vector<vector<int>>, compare> pq;

		fill(cost.begin(), cost.end(), INF);
		fill(visit.begin(), visit.end(), false);

		cost[s] = 0;

		while (true) {
			visit[s] = true;
			for (int i = 0; i < adj[s].size(); i++) {
				int nextVrt = adj[s][i].first;
				int nextCost = adj[s][i].second;
				if (!visit[nextVrt] && (nextCost + cost[s] < cost[nextVrt])) {
					cost[nextVrt] = nextCost + cost[s];
					pq.push({ s, nextVrt, cost[nextVrt] });
				}
			}

			while (pq.size() > 0) {
				s = pq.top()[1];
				int e = pq.top()[0];
				pq.pop();
				if (!visit[s]) {
					selectedEdge.push_back(make_pair(e, s));
					break;
				}
			}

			if (pq.size() == 0)
				break;
		}
	}
};

int main() {
	graph g;
	int n, m;
	int u, v, c;
	scanf("%d %d", &n, &m);
	g.init(n);
	
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &u, &v, &c);
		g.addEdge(u - 1, v - 1, c);
	}

	g.dijkstra(0);
	
	printf("%d\n", g.selectedEdge.size());
    
	int *ptr = NULL;
	if (g.selectedEdge.size() < n - 1)
		printf("%d", *ptr);
    
	for (int i = 0; i < g.selectedEdge.size(); i++) {
		printf("%d %d\n", g.selectedEdge[i].first + 1, g.selectedEdge[i].second + 1);
	}
}

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

문제

문제

출처

ICPC

어떤 케이스에서 오류가 나는지를 모르겠네요..

ljjk159 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말