글 읽기 - 반례 도저히 못찾겠습니다 ㅠㅠ [c++]

loveto3 4년 전 0

반례랑 예시는 다 맞는거같은데;;

한 5퍼센트에서 틀렸다고 나오네요 ㅠㅠ

반례나 틀린부분 지적좀 부탁드립니다.

// 다익스트라 데뷔전

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

int main() {
	int v, e, k;
	cin >> v >> e >> k;
	int max = 30000010;
	int* check = new int[v]{ 0}; //체크 배열 0으로 초기화
	int* dp = new int[v] {max};
	
	fill(dp, dp + v, max); // 시작노드는 0, 나머지는 무한대로 초기화.
	dp[k-1] = 0;
	vector<vector<pair<int, int> > > mp;  // 2차원 vector 생성
	for (int i = 0; i < v+1; i++) {
		vector<pair <int ,int> >  red;
		mp.push_back(red);
	}

	//v[u]에 v와 w를 페어로 저장.
	for (int i = 0; i < e; i++) {
		int v1, e1, k1;
		cin >> v1 >> e1 >> k1;
		mp[v1].push_back(make_pair(e1, k1));
		//mp[e1].push_back(make_pair(v1, k1));
	}
	//cout << "flag1" << '\n';
	// dp값과 정점을 페어로 하는 최소우선순위큐
	priority_queue<pair<int , int>,vector<pair<int,int>> ,greater<pair<int,int> > > pq;
	pq.push(make_pair(0,k - 1));
	
	while (!pq.empty()) {
		
		int top = pq.top().second;
		
		pq.pop();
		if (check[top] == 0) {
			
			for (auto k : mp[top+1]) {
				
				
					if (dp[top] + k.second < dp[k.first - 1]) {
						dp[k.first - 1] = dp[top] + k.second;
					}

					pq.push(make_pair(dp[k.first], k.first - 1));
				
			}

			check[top] = 1;
		}
	}

	//cout << "======dp =======\n";
	for (int i = 0; i < v; i++) {
		if (dp[i] == max) {
			cout << "INF" << '\n';
			continue;
		}
		cout << dp[i] << '\n';
	}
	/*cout << "\n=========mp=====\n";
	for (auto k : mp) {
		for (auto h : k) {
			cout << h.first << ","<<h.second<<"  ";
		}
		cout << '\n';
	}
	cout << "\n========check====\n";
	for (int i = 0; i < v; i++) {
		cout << check[i] << " ";
	}
*/
	
}

opop20207 4년 전 0

check를 해주신 이유는 무엇인가요?

코드에서 check를 제외해주고 다익스트라를 짜니까 AC를 받았습니다.

다익스트라 알고리즘 상 check를 해줄 필요가 없네요...

loveto3 4년 전 0

체크 안하면 벨만포드 알고리즘이고 체크를 해야 다익스트라 알고리즘 아닌가여?

체크하면서 맞고싶은데 ㅠㅠ

loveto3 4년 전 0

if (dp[top] + k.second < dp[k.first - 1]) {
dp[k.first - 1] = dp[top] + k.second;
}

pq.push(make_pair(dp[k.first-1], k.first - 1));

}

이부분에서 make_pair(dp[k.first-1] 을 해야되는데 k.first를 넣었었네요 @@;

해결됐습니다! 답변감사합니다~

opop20207 4년 전 3

그렇군요 더 자세히 알고 봤어야했는데 미숙한 조언 드려서 죄송합니다.

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

문제

문제

출처

ICPC

반례 도저히 못찾겠습니다 ㅠㅠ [c++]

loveto3 4년 전 0

opop20207 4년 전 0

loveto3 4년 전 0

loveto3 4년 전 0

opop20207 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말