글 읽기 - C++ 33%에서 틀렸다고 합니다

av3rs1on 2년 전 0

s->g->h->x OR s->h->g->x 가는 케이스 2개를 구해 s->x로 가는 결과값과 동일하다면 vector에 넣어 출력하는 식으로 구현했습니다.

s==g 인 경우나 s==h인 경우에도 s->h->x, s->g->x로 따로 빼어 겹치지 않게 하였는데 어디서 틀린건지 잘 모르겠습니다

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

#define INF 2147483646
using namespace std;
int tc, n, m, t, s, g, h, a, b, d, x;
vector<pair<int, int>> v[2002];
int dist[2002];

vector<int> r;

//다익스트라
int dijk(int start, int end) {
	//거리 초기화
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;//우선순위 큐, 정점, 거리
	pq.push({ 0, start });

	//bfs
	while (!pq.empty()) {
		//현재위치
		int cost = -pq.top().first;//거리,최소힙 기능
		int city = pq.top().second;//정점
		pq.pop();

		//이전 값보다 큼 => 다음으로 넘어감,계산 불필요
		if (dist[city] < cost) {
			continue;
		}

		//이웃 탐색
		for (int i = 0; i < v[city].size(); i++) {
			int next = v[city][i].first;//다음 정점
			int next_cost = v[city][i].second;//다음 거리

			//최소경로 발생시 업데이트
			if (dist[next] > cost + next_cost) {
				dist[next] = cost + next_cost;
				pq.push({ -dist[next] , next });
			}
		}
	}
	//끝점에서의 최단거리
	return dist[end];
}

int main(void) {
	cin >> tc;

	for (int i = 0; i < tc; i++) {
		cin >> n >> m >> t;
		// n = 교차로수,  m = 도로,  t = 목적지 후보 수
		cin >> s >> g >> h;
		// s = 출발지,  g - h = 냄새를 맡은 도로
		for (int j = 0; j < 2001; j++)
			v[i].clear();
		fill(dist, dist + 2001, INF);
		for (int j = 0; j < m; j++) {
			//이후 m줄동안 a<->b 간선정보 업데이트
			cin >> a >> b >> d;
			// a<->b,  cost = d
			v[a].push_back({ b,d });
			v[b].push_back({ a,d });
		}
		for (int j = 0; j < t; j++) {
			//이후 t줄동안 후보지 정보 업데이트
			cin >> x;
			int aa, bb, rr;
			//최단 경로가 s - a - b - x 또는 s - b - a - x 일경우 정답.
			//매 시행마다 dist 초기화
			rr = dijk(s, x);
			if (s == g)
				aa = dijk(s, h) + dijk(h, x);
			else
				aa = dijk(s, g) + dijk(g, h) + dijk(h, x);
			if (s == h)
				bb = dijk(s, g) + dijk(g, x);
			else
				bb = dijk(s, h) + dijk(h, g) + dijk(g, x);
			if (rr == aa || rr == bb) {
				r.push_back(x);
			}
		}
		sort(r.begin(), r.end());

		for (int j = 0; j < r.size(); j++)
			cout << r[j] << " ";

		r.clear();
		cout << '\n';
	}
}

tkdgus0782 2년 전 0

주석에는 시행마다 dist초기화라고 되어있는데, 코드에는 시행마다 dist를 초기화하는 부분이 없는 것 같습니다.

dist[start] = 0 ;만 초기화 할게 아니라,

매시행마다 start를 제외한 dist전체를 INF로 초기화해주거나, dist를 지역변수로 선언하면 될것 같네요.

0archlinux0 2년 전 0

s->g->h->x OR s->h->g->x 경로의 가중치 합 = s->x 을 출력, 두가지의 예외 처리만 해주면 됩니다

Edge case:

1) s == g or s == h

2) x == g or x == h

1의 경우 s->h->x, s->g->x로 따로 빼어 겹치지 않게 처리하셨다고 쓰셨는데 더 단순한 방법으로는 s에서s로 가는 가중치값을 미리 0으로 초기화,

2의 경우는 g에서 g, h에서 h로 가는 가중치값을 미리 0으로 처리함으로써 해결 할 수 있습니다.

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

문제

문제

출처

ICPC

C++ 33%에서 틀렸다고 합니다

av3rs1on 2년 전 0

tkdgus0782 2년 전 0

0archlinux0 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말