글 읽기 - 반례즘 부탁드리겠습니다. (주석 있음)

knight7024 3년 전 0

다익스트라를 두 번 돌린 후 각 장소 별로 거리를 비교하는 작업을 수행했습니다.

조건의 순서가,

1. 지헌이가 걸리는 최단 시간과 성하가 걸리는 최단 시간의 합이 최소가 되도록

2. 새로운 약속 장소에 지헌이가 먼저 도착하거나 지헌이와 성하는 동시에 도착

3. 지헌이가 가장 적은 시간동안 움직이는 곳

4. 장소 번호가 가장 작은 것

이기에 튜플로 넣은 뒤 정렬하는 방법을 이용했습니다.

게시판의 반례들은 모두 맞게 나오는 데 8%에서 틀립니다. 어디가 문제일까요?

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

const int INF = 0x3f3f3f3f;

void dijkstra(int start, vector<vector<pair<int, int>>>& adj, int minDist[]) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({0, start});
	minDist[start] = 0;

	while (!pq.empty()) {
		auto front = pq.top();
		pq.pop();

		int nowNode = front.second;
		int nowDist = front.first;
		if (minDist[nowNode] < nowDist) continue;

		for (auto& v : adj[nowNode]) {
			int nextNode = v.first;
			int nextDist = v.second + nowDist;
			if (minDist[nextNode] > nextDist) {
				minDist[nextNode] = nextDist;
				pq.push({nextDist, nextNode});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int v, m;
	cin >> v >> m;

	vector<vector<pair<int, int>>> adj(v + 1);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}

	int j, s;
	cin >> j >> s;

	int jDist[101];
	memset(jDist, INF, sizeof(jDist));
	int sDist[101];
	memset(sDist, INF, sizeof(sDist));

	dijkstra(j, adj, jDist);
	dijkstra(s, adj, sDist);

	int minSum = INF;
	// 지헌이가 걸리는 시간 + 성하가 걸리는 시간, 지헌이가 걸리는 시간, 약속 장소
	vector<tuple<int, int, int>> result;
	// 지헌이와 성하의 최단 거리 각각 확인한다.
	for (int i = 1; i <= v; i++) {
		// 1. 지헌이와 성하의 출발지 제외
		if (i == j || i == s) continue;
		// 2. 합의 최소 구하기
		// 3. 지헌이가 더 빨리 도착해야 하거나 동시에 도착해야 함
		if (minSum >= jDist[i] + sDist[i] && jDist[i] <= sDist[i]) {
			minSum = jDist[i] + sDist[i];
			result.push_back({minSum, jDist[i], i});
		}
	}

	sort(result.begin(), result.end());

	cout << (result.empty() ? -1 : get<2>(result[0]));
	return 0;
}

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

문제

문제

출처

ICPC

반례즘 부탁드리겠습니다. (주석 있음)

knight7024 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말