글 읽기 - 틀렸습니다. 혹시 고수님들 코드 한번 살펴봐주실수 있으실까요.

jangtai4 1년 전 0

온라인 컴파일러까지 동원하였으나, 미천한 저는 해답을 찾지 못하였습니다.

많은 입력 예시들을 동원하였으나, 홀로 잘못된 부분을 깨닫기 힘들 것 같습니다.

간곡히 부탁드립니다 고수님들 도와주십시요.

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> Pair;
int min_cost[20001];
priority_queue<Pair, vector<Pair>, greater<Pair>> buff[20001];

void revise_min_cost(int start) {
	while (!buff[start].empty()) {
		Pair temp;
		temp = buff[start].top();
		buff[start].pop();
		int cost = temp.first;
		int departure = temp.second;
		if (min_cost[departure] > min_cost[start] + cost) {
			min_cost[departure] = min_cost[start] + cost;
			revise_min_cost(departure);
		}
		
	}
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int V, E;
	int start;
	int home, departure, cost;
	cin >> V >> E >> start;

	for (int i = 0; i < V + 1; i++) {
		min_cost[i] = INT_MAX;
	}
	for (int i = 0; i < E; i++) {
		cin >> home >> departure >> cost;
		Pair p = { cost,departure };
		buff[home].push(p);
	}

	min_cost[start] = 0;
	
	revise_min_cost(start);

	for (int i = 1; i < V; i++) {
		if (min_cost[i] == INT_MAX) {
			cout << "INF\n";
		}
		else {
			cout << min_cost[i] << '\n';
		}
		
	}
	cout << min_cost[V];
	


	

}

jangtai4 1년 전 0

다른 분들 질문글 참고하여 아예 자료구조를 바꾸어봤는데 이것 또한 틀렸다고 뜨네요 ..

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

typedef tuple<int, int, int> Tuple;

vector<Tuple> buffer[20001];
int min_distance[20001];




int main() {
	int V, E, K;
	int u, v, w;
	priority_queue <Tuple, vector<Tuple>, greater<Tuple>> pq;
	vector<int> depart_vector;
	cin >> V >> E >> K;

	for (int i = 0; i < V + 1; i++) {
		min_distance[i] = INT_MAX;
	}

	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		Tuple temp_tuple;
		temp_tuple = { w,u,v };
		buffer[u].push_back(temp_tuple);
	}

	min_distance[K] = 0;
	while (!buffer[K].empty()) {
		pq.push(buffer[K].back());
		buffer[K].pop_back();
	}

	while (true) {
		
		
		while (!pq.empty()) { // 수정
			Tuple temp = pq.top();
			pq.pop();

			int w1, u1, v1;
			w1 = get<0>(temp);
			u1 = get<1>(temp);
			v1 = get<2>(temp);
			depart_vector.push_back(v1);

			if (min_distance[v1] > min_distance[u1] + w1) {
				min_distance[v1] = min_distance[u1] + w1;
			}
		}
		while (!depart_vector.empty()) { // 다시 집어넣기
			int K = depart_vector.back();
			depart_vector.pop_back();
			while (!buffer[K].empty()) {
				Tuple temp = buffer[K].back();
				buffer[K].pop_back();
				pq.push(temp);
			}
		}
			
		if (pq.empty()) {
			break;
		}

		

	}
	for (int i = 1; i < V + 1; i++) {
		if (min_distance[i] == INT_MAX) {
			cout << "INF" << '\n';
		}
		else {
			cout << min_distance[i] << '\n';
		}
		
	}

	return 0;
}

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

문제

문제

출처

ICPC

틀렸습니다. 혹시 고수님들 코드 한번 살펴봐주실수 있으실까요.

jangtai4 1년 전 0

jangtai4 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말