글 읽기 - 도와주세요.. 틀렸습니다

kengh2472 5년 전 0

우선순위큐를 사용하지 않고 구현하였습니다. 시간초과는 뜨지 않는데 틀렸습니다가 나오네요..

게시판에 있는 테스트케이스는 전부 맞는데 다른 부분의 오류를 모르겠습니다.

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

using namespace std;
#define Inf 987654321
int V, E, start;
int dt[20001], visit[20001];
vector<pair<int, int> > v[20001];

void func() {
	queue<int> q;
	q.push(start);

	while (1) {
		int size = q.size();

		if (size == 0)
			break;

		int sv = q.front();
		q.pop();

		for (int i = 0; i < v[sv].size(); i++) {
			if(visit[v[sv][i].first] == 0){
				visit[v[sv][i].first] = 1;
				if (dt[v[sv][i].first] > v[sv][i].second + dt[sv]) {
					dt[v[sv][i].first] = v[sv][i].second + dt[sv];
				}
				q.push(v[sv][i].first);
			}
			//한 점에서 두번째 방문시 길이 체크
			else if (visit[v[sv][i].first] == 1) {
				if (dt[v[sv][i].first] > v[sv][i].second + dt[sv]) {
					dt[v[sv][i].first] = v[sv][i].second + dt[sv];
				}
			}

		}

	}

}

int main() {
	scanf("%d %d", &V, &E);
	scanf("%d", &start);

	for (int i = 0; i < E; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		v[a].push_back(pair<int, int>(b, c));

	}

	for (int i = 1; i <= V; i++)
		dt[i] = Inf;
	dt[start] = 0;
	//func
	func();

	for (int i = 1; i <= V; i++){
		if (dt[i] == Inf)
			printf("INF\n");
		else
			printf("%d\n", dt[i]);
	}


	return 0;
}

djm03178 5년 전 1

두 번째 방문 때 거리만 갱신해주는 걸로는 불충분합니다.

https://ideone.com/W945Yd

kengh2472 5년 전 0

처음에 1을 방문하고 2와 3을 큐에 넣었을 때, 거리가 짧은 3먼저 해야 하는데 2를 먼저 체크해서 값이 다르게 나오네요..

다음 3에서 2를 초기화한다 하지만 2를 다시 큐에넣지 않아서 4를 방문하지않고..

우선순위 큐를 공부한 뒤 다시 풀어보겠습니다. 감사합니다.

kengh2472 5년 전 0

우선순위 큐를 사용하여 새로 구현했습니다.

visit대신에 distance배열을 사용하여 방문여부와 거리를 같이 해결했습니다.

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

#define INF 987654321

vector<pair<int, int> > v[20001];

int V, E, dt[20001];

void bfs(int start) {
	int vc = 1;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
	pq.push(pair<int, int>(0,start));

	while (!pq.empty()) {
		//방문 체크
		int fr = pq.top().second;
		pq.pop();

		for (int i = 0; i < v[fr].size(); i++) {
			//미방문 
			if (dt[v[fr][i].second] > v[fr][i].first + dt[fr]) {
				dt[v[fr][i].second] = v[fr][i].first + dt[fr];
				pq.push(pair<int,int>(dt[v[fr][i].second], v[fr][i].second));
			}

		}

	}

}

int main(void) {
	scanf("%d %d", &V, &E);
	for (int i = 1; i <= V; i++)
		dt[i] = INF;
	int start;
	scanf("%d", &start);
	dt[start] = 0;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		v[a].push_back(pair<int, int>(c, b));
	}

	//bfs
	bfs(start);
	for (int i = 1; i <= V; i++) {
		if (dt[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", dt[i]);
	}

	return 0;
}

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

문제

문제

출처

ICPC

도와주세요.. 틀렸습니다

kengh2472 5년 전 0

djm03178 5년 전 1

kengh2472 5년 전 0

kengh2472 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말