글 읽기 - 자료형 범위 질문

iron1209 5년 전 0

저는 처음에 입력을 받을때 가중치를 2배를 default 로하여 여우가 지나갈때, 늑대가 빠르게 갈때는 반으로, 늑대가 느리게 갈때는 2배로 해서 최소 1(2*1/2)배, 최대 4(2*2)배가 되도록 했습니다.

그런데 여기서 지나갈때 걸리는 가중치가 각각 최대 100,000이라고 하고 최대 노드의 개수가 4,000개라고 한 뒤에 모든 길을 늑대가 느리게 간다고 가정한다면 4*100,000*4,000 = 16억 이 나오는데, 이는 int 로 커버할 수 있다고 생각합니다. 그런데 처음엔 int로 제출해서 틀렸다가 long long 으로 바꾸니 되더군요. 왜 그런진 모르겠지만 ㅡㅡ 🤔

제 생각엔 비둘기집 이론(?) 때문에 최단거리로 가는건 한 노드를 한번만 방문하는걸로 알고있는데 혹시 제가 실수한 부분이 있을까요?

------추가-------------

밑의 코드는 정답통과한 코드입니다. (수정함) "이 부분이 int 여도 되지 않을까요?" 라고한 부분은 원래 int 였어요. 제 질문은 저 부분들이 최대 16억일테니 int로 다 표현할 수 있을텐데 왜 int로 하면 틀리고 long long으로 하면 맞나 이걸 질문하는겁니다. 최대 가중치가 16억을 넘을 수 있나요? 이제와서 보니 질문이 좀 이상했네요.

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
typedef struct wolf {
	long long record; //이 부분이 int 여도 되지 않을까요?
	int node;
	bool fast; //0은 느림 1은 빠름
};
bool operator < (wolf a, wolf b) {
	return a.record < b.record;
}
int n, m;
long long dp_f[4003], dp_wf[4003], dp_ws[4003]; // 이 부분도 int여도 되지 않을까요?
vector <pair<int, long long>> con[4003];
priority_queue <wolf> wolf_q;
priority_queue <pair<long long, int>> fox_q;
long long min(long long a, long long b) {
	return a < b ? a : b;
}
int main() {
//	freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	while (m--) {
		int a, b;
		long long c;
		scanf("%d %d %lld", &a, &b, &c);
		con[a].push_back({ b,c * 2 }); //이 부분에서 가중치를 2배로 받음
		con[b].push_back({ a,c * 2 }); //이 부분에서도
	}
	for (int i = 1; i <= n; i++) dp_f[i] = dp_ws[i] = dp_wf[i] = 1e17;
	dp_f[1] = 0;
	fox_q.push({ 0,1 });
	while (!fox_q.empty()) {
		long long cost = -1 * fox_q.top().first;
		int now = fox_q.top().second;
		fox_q.pop();
		if (cost != dp_f[now]) continue;
		for (auto i : con[now]) {
			int next = i.first;
			if (dp_f[now] + i.second < dp_f[next]) {
				dp_f[next] = dp_f[now] + i.second;
				fox_q.push({ -1 * dp_f[next], next });
			}
		}
	}
	wolf_q.push({ 0,1,true });
	dp_ws[1] = 0;
	while (!wolf_q.empty()) {
		int now = wolf_q.top().node;
		long long record = -1 * wolf_q.top().record;
		bool fast = wolf_q.top().fast;
		wolf_q.pop();
		if (fast) {
			if (dp_ws[now] != record) continue;
		}
		else {
			if (dp_wf[now] != record) continue;
		}
		for (auto i : con[now]) {
			if (fast) { //늑대가 빠르게갈때는 가중치 반으로 해서 더해줌
				int next = i.first;
				if (dp_ws[now] + (i.second / 2) < dp_wf[next]) {
					dp_wf[next] = dp_ws[now] + (i.second / 2);
					wolf_q.push({ -1 * dp_wf[next],next, false });
				}
			}
			else { //늑대가 느리게 갈때는 가중치 2배로 해서 더해줌
				int next = i.first;
				if (dp_wf[now] + (i.second * 2) < dp_ws[next]) {
					dp_ws[next] = dp_wf[now] + (i.second * 2);
					wolf_q.push({ -1 * dp_ws[next],next, true });
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (dp_f[i] < min(dp_wf[i], dp_ws[i])) ans++;
	}
	printf("%d", ans);
}

djm03178 5년 전 1

질문을 잘 이해하지 못하겠는데, 조금 더 명확하게 해주셨으면 합니다.

이 코드에서는 int가 아니라 long long을 사용하고 있는데, 그러면 이 코드는 맞는 코드라는 뜻인가요? 그런데 제출해 보면 (freopen 지우고) 시간 초과가 나옵니다.

올리신 코드가 정확히 어떤 상태의 코드이고, 어떤 채점 결과를 받은 코드이며, 변경한 부분이 어디어디인지 등에 대한 구체적인 설명을 해주셔야 답변을 해드릴 수 있을 것 같습니다.

iron1209 5년 전 0

앗 죄송합니다. 새벽 늦은 시간에 질문을 해서 그런지 비몽사몽한 상태로 질문을 해버렸네요.

올린 코드는 정답인 코드입니다. (수정함) "이 부분이 int 여도 되지 않을까요?" 라고한 부분은 원래 int 였어요. 제 질문은 저 부분들이 최대 16억일테니 int로 다 표현할 수 있을텐데 왜 int로 하면 틀리고 long long으로 하면 맞나 이걸 질문하는겁니다. 아마 최대가 16억 이라는 저의 전제가 틀린것 같아서 질문드려요

djm03178 5년 전 1

말씀하신 곳 7, 15번째 줄을 int로 바꾸고, 32번째 줄을 2e9로 바꾸니 통과됩니다.

그리고 질문 시에는 맞은 코드보다는 틀린 코드를 그대로 보여주는 편이 좋습니다. 맞은 코드야 어쨌든 문제가 없어서 맞은 것이니, 틀린 부분을 찾으려면 틀린 코드를 봐야 원인을 찾을 수 있습니다.

iron1209 5년 전 0

오 감사합니다. 다른 사람이랑 코드를 돌려보니 에러를 금방 잡네요. 저런데서 실수를하다니 ㅡㅡ

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

문제

문제

출처

ICPC

자료형 범위 질문

iron1209 5년 전 0

djm03178 5년 전 1

iron1209 5년 전 0

djm03178 5년 전 1

iron1209 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말