글 읽기 - AC는 받았는데 이해가 가지않는 부분이 있어서 한번만 도와주세요!!

dntjd1081 4년 전 0

다익스트라 내부에서 dist 배열을 INF로 초기화하는데 이 INF를 해당 코드에서처럼 signed int의 최대치로 설정해놓으면 틀렸습니다가 나와서 다른 분들처럼 200000000로 초기화했더니 AC가 나오네요?....

다익스트라 내부에서 dist배열에 더하는 과정이 따로없어서 오버플로우는 나지않는거같은데 왜 이런건가요? ㅠㅠㅠ도와주십쇼

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

const int INF = numeric_limits<int>::max(); //200000000;

vector<vector<pair<int, int>>>adj;

void dijkstra(const vector<int>&candidates,int S) {
	vector<int>dist(adj.size(), INF);
	priority_queue<pair<int, int>>pq;
	dist[S] = 0;
	pq.push({ 0,S });

	while (!pq.empty()) {
		int cost = -pq.top().first, here = pq.top().second;
		pq.pop();

		if (cost > dist[here])
			continue;

		for (int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (nextCost < dist[there]) {
				dist[there] = nextCost;
				pq.push({ -nextCost,there });
			}
		}
	}

	vector<int>ans;
	for (auto it : candidates)
		if (dist[it] % 2 != 0)
			ans.push_back(it);
	sort(ans.begin(), ans.end());
	for (auto it : ans)
		cout << it << " ";
	cout << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int C;
	cin >> C;
	while (C--) {
		int N, M, T, S, G, H;
		cin >> N >> M >> T >> S >> G >> H;
		for (int i = 0; i < adj.size(); ++i)
			adj[i].clear();
		adj.clear();
		adj = vector<vector<pair<int, int>>>(N + 1);

		while (M--) {
			int a, b, d;
			cin >> a >> b >> d;
			d *= 2;
			if ((a == G && b == H) || (a == H && b == G))
				d -= 1;
			adj[a].push_back({ b,d });
			adj[b].push_back({ a,d });
		}

		vector<int>candidates(T);
		for (int i = 0; i < T; ++i)
			cin >> candidates[i];

		dijkstra(candidates, S);
	}
}

3587jjh 4년 전 2

38째줄에서 거리가 INF인 정점이 걸러지느냐 아니냐로 정답이 갈리는것 같습니다

dntjd1081 4년 전 0

감사합니다 ㅜㅜ 그 점을 간과하고있었네요! 정말 감사합니다~!

djm03178 4년 전 2

signed가 아니라 unsigned가 2^32-1까지입니다. 그냥 int가 곧 signed int입니다.

atomzeno 3년 전 0

윗분 말씀이 맞습니다!

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

문제

문제

출처

ICPC

AC는 받았는데 이해가 가지않는 부분이 있어서 한번만 도와주세요!!

dntjd1081 4년 전 0

3587jjh 4년 전 2

dntjd1081 4년 전 0

djm03178 4년 전 2

atomzeno 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말