글 읽기 - 8%에서 틀렸다고 나옵니다(다익스트라)

piy0605 5년 전 0

w_v로 최소 가중치를 저장,
check로 체크리스트를 저장
graph에 값들을 저장
a로 현재 노드가 가야할 벡터들을 저장해서, 다음 검사 때, 그 벡터값들 중 검사

중복 간선 최소값으로 하게끔 값을 저장했고,

게시글에 나오는 반례값들도 확인해본 것에 한해서는 잘 나왔습니다.

8%면 어디서 놓친걸까요..

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int sortman(pair<int, int>p1, pair<int, int>p2) {
	return p1.first < p2.first;
}

int main() {
	int V, E, s;
	scanf("%d %d %d", &V, &E, &s);
	vector<vector<pair<int, int>>>graph(V, vector<pair<int, int>>(0));
	vector<int> check(V, 0);
	vector<int> w_v(V, 10000001);
	vector<int> a(0);
	w_v[s - 1] = 0;
	a.push_back(s - 1);
	for (auto i = 0; i < E; i++) {
		int se, ee, w;
		scanf("%d %d %d", &se, &ee, &w);
		graph[se - 1].push_back(make_pair(ee - 1, w));
	}

	for (auto i = 0; i < V; i++)sort(graph[i].begin(), graph[i].end(), sortman);

	while (1) {
		int min = 10000000, idx = -1;
		for (auto j = 0; j < a.size(); j++) {
			if (min > w_v[a[j]] && !check[a[j]]) {
				idx = a[j];
				min = w_v[a[j]];
			}
		}

		a.clear();
		if (min == 10000000)break;
		for (auto j = 0; j < graph[idx].size(); j++) {
			if (j != graph[idx].size() - 1) {
				if (graph[idx][j].first == graph[idx][j + 1].first) {
					if (graph[idx][j].second > graph[idx][j + 1].second) {
						graph[idx][j].second = graph[idx][j + 1].second;
					}
					graph[idx].erase(graph[idx].begin() + j + 1);
					j--;
					continue;
				}
			}
			if (w_v[graph[idx][j].first]>graph[idx][j].second + w_v[idx]) {
				w_v[graph[idx][j].first] = graph[idx][j].second + w_v[idx];
				a.push_back(graph[idx][j].first);
			}
		}
		check[idx] = 1;
	}
	for (auto i = 0; i < V; i++) {
		if (w_v[i] != 10000001)printf("%d\n", w_v[i]);
		else printf("INF\n");
	}

	return 0;
}

djm03178 5년 전 4

반례입니다.

4 5
1
1 3 2
3 2 4
1 4 2
4 2 1
1 3 5
output: 0 6 2 2
correct answer: 0 3 2 2

piy0605 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

8%에서 틀렸다고 나옵니다(다익스트라)

piy0605 5년 전 0

djm03178 5년 전 4

piy0605 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말