글 읽기 - 답은 맞았는데 자료형 다루는 것에 대해 궁금한 게 있습니다. 코드 있어요

dmzld 3년 전 0

다익스트라 알고리즘에서

시작 노드부터 i번째 노드까지 최단 경로를 D[i] 배열로 표현하고 INT_MAX로 초기화 시켰는데요

마지막에 최단 경로가 존재하는지 판별하는 부분을 간단하게 하고자

A =( R1[v1] + R2[v2] + R3[N], R1[v2] + R3[v1] + R2[N]);

if (A1 >= INT_MAX || A1 < 0)
cout << -1;
else
cout << A;

이런 식으로 했더니 틀리더라구요

INT형 변수에 담긴 INT_MAX 끼리 더하면(즉 INT_MAX + INT_MAX)

다른 INT형 변수에 저장하기전에 어떻게 존재하나요?

저장한 후에는 음의 값을 가지는 쓰레기값이 되는 것으로 알고 있습니다.

그리고 이런 특성을 고려했을 때 코드를 더 간단하게 할 수 없을까요?

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <climits>

using namespace std;

int N, E, u, v, w, v1, v2;
vector<pair<int, int>> G[801]; //  pair<v, w> G[u]
vector<int> R1, R2, R3;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // for dijkstra
int A1, A2;

vector<int> dijkstra(int start){

	vector<int> D(N + 1, INT_MAX);
	D[start] = 0; // starting point

	pq.push({ 0, start }); // from starting point
	while (!pq.empty()){
		int weight = pq.top().first;
		int from = pq.top().second;
		pq.pop();

		if (D[from] < weight)
			continue;

		for (int i = 0; i < G[from].size(); i++){
			int to = G[from][i].first; // vertex can be arrived
			int nWeight = G[from][i].second;

			if (D[to] > nWeight + weight){ // distance of K ~ from ~ to
				D[to] = nWeight + weight; // update min distance K to to
				pq.push({ nWeight + weight, to });
			}
		}
	}
	return D;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> E;

	for (int i = 0; i < E; i++){
		cin >> u >> v >> w;
		G[u].push_back({ v, w });
		G[v].push_back({ u, w });
	}
	cin >> v1 >> v2;

	R1 = dijkstra(1); // 1 to v1, 1 to v2
	R2 = dijkstra(v1); // v1 to v2, v1 to N
	R3 = dijkstra(v2); // v2 to v1, v2 to N

    /*
﻿    A =( R1[v1] + R2[v2] + R3[N], R1[v2] + R3[v1] + R2[N]);

    if (A1 >= INT_MAX || A1 < 0)
        cout << -1;
    else
        cout << A;
    */
    // 이 부분부터 더 간결하게 바꾸고 싶음
	A1 = (R1[v1] != INT_MAX && R2[v2] != INT_MAX && R3[N] != INT_MAX) ? R1[v1] + R2[v2] + R3[N] : INT_MAX;
	A2 = (R1[v2] != INT_MAX && R3[v1] != INT_MAX && R2[N] != INT_MAX) ? R1[v2] + R3[v1] + R2[N] : INT_MAX;

	if (A1 == INT_MAX&&A2 == INT_MAX)
		cout << -1;
	else
		cout << min(A1, A2);

	return 0;
}

ckdgus2482 3년 전 1

rvalue라고 하더라도 자료형은 있습니다.

INT_MAX 정의부분을 봐야 알겠지만 int 타입이라면 + 연산 전에 더 큰 타입으로 명시적 캐스팅을 하지 않으면 산술 오버플로가 발생하겠죠

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

문제

문제

출처

ICPC

답은 맞았는데 자료형 다루는 것에 대해 궁금한 게 있습니다. 코드 있어요

dmzld 3년 전 0

ckdgus2482 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말