글 읽기 - 풀이가 잘못된 건지 궁금합니다

degurii 4년 전 0

모든 간선의 비용에 *2를 해준 뒤, g-h를 잇는 간선에만 -1을 해줬습니다.

이렇게 하면 g-h를 지나게 되는 최단거리는 홀수로 나오게 되어 그런 정점만 답에 추가했는데요

틀렸습니다가 뜨는데 문제가 있을까요?

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f

int T;
struct Node {
	int to, cost;
	Node(int t = 0, int c = 0) :to(t), cost(c) {}
};
int n, m, t, s, g, h;
vector<vector<Node>> p;
vector<int> dist, ans;

void dijkstra(int st) {
	priority_queue<pair<int, int>> q;
	dist[st] = 0;
	q.push({ -dist[st], st });
	while (!q.empty()) {
		auto[cost, now] = q.top();
		q.pop();
		if (-cost > dist[now]) continue;
		for (auto e : p[now]) {
			auto[next, ncost] = e;
			if (dist[next] > dist[now] + ncost) {
				dist[next] = dist[now] + ncost;
				q.push({ -dist[next], next });
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while (T--) {
		p.clear();
		ans.clear();
		dist.clear();
        
		cin >> n >> m >> t;
		p.resize(n + 1);
		dist.resize(n + 1, INF);
		cin >> s >> g >> h;
        
		for (int i = 0; i < m; i++) {
			int u, v, c;
			cin >> u >> v >> c;
			c *= 2;
			if ((u == g && v == h) || (u == h && v == g)) c--;
			p[u].emplace_back(v, c);
			p[v].emplace_back(u, c);
		}
		dijkstra(s);
		for (int i = 0; i < t; i++) {
			int x;
			cin >> x;
			if (dist[x] & 1) ans.push_back(x);
		}
		sort(ans.begin(), ans.end());
		for (int x : ans) {
			cout << x << ' ';
		}
		cout << '\n';
	}
}

yskang 4년 전 1

특정지점까지 최단거리 경로가 두개 이상인 경우, 다잌스트라로 구한 최단 경로는 여러개의 최단 경로 중 하나일 것 입니다.

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

문제

문제

출처

ICPC

풀이가 잘못된 건지 궁금합니다

degurii 4년 전 0

yskang 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말