글 읽기 - 답이 왜 long long type이 필요한지 모르겠어요 ㅜㅜ

kimeun0 6년 전 2

int로 하고 INF를 1000000000 (1e9)로 하거나

2087654321 로 하면 50%쯤에서 틀리고 long long으로 해야만 맞습니다.

그런데 교통비가 최대 백만이고 경로도 최대 100개인데

최대 길어봐야 int의 max인 10의 9승까지는 안가고 10의 8승이면 전체 경로합이 계산되는데

왜 long long 이 필요할까요?

경로합을 갱신할때도 from의 경로합이 아직 INF면 계산안하기 때문에 INF와 연산식이 있는것도 아닌데...

아무리 생각해도 이해가 잘 안가서 질문올려 봅니다.

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

struct edge {
	int from;
	int to;
	int cost;
	edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
};
const long long INF = 1LL<<60;

vector<edge> Edge;
long long D[100];
int R[100][100];
int Money[100];


int main() {

	int N, Start, End, M;

	scanf("%d %d %d %d", &N, &Start, &End, &M);
//	Edge = vector<vector<edge>>(M + 1);
	memset(R, 0, sizeof(R));

	for (int i = 1; i <= M; i++) {
		int x, y, z;

		scanf("%d %d %d", &x, &y, &z);
		Edge.push_back(edge(x,y, z));
		R[x][y] = 1;
	}

	for (int i = 0; i < N; i++) {
		scanf("%d", &Money[i]);
	R[i][i] = 1;
	}

	fill(D, D + N, INF);

	for (int k = 0; k < N; k++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (R[i][k] && R[k][j]) R[i][j] = 1;

	D[Start] = -Money[Start];

	int Gee = 0; int gg = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int node = Edge[j].from;
			int next = Edge[j].to;
			int next_cost = Edge[j].cost;
			if (D[node] != INF && D[next] > D[node] + next_cost - Money[next]) {
					D[next] = D[node] + next_cost - Money[next];
			if (i == N - 1 && R[next][End] == 1) Gee = 1;
			}
		}
	}

	if (D[End] == INF)  gg = 1;
	if (Gee == 1) puts("Gee");
	else if (gg == 1) puts("gg");
	else printf("%lld\n", -D[End]);

	return 0;
}

namhong2001 5년 전 0

사이클이 있는 경우 계산값이 무척 작아질 수 있기 때문입니다. 위 코드에서 D[node]가 어느순간 무척 작은 값을 가지게 되었고 D[node] + next_cost - Money[next] 가 오버플로우를 일으켜 무척 큰값이 되는 경우를 생각해 볼 수 있습니다. 이 경우 D[next]는 더이상 업데이트 되지 않고 사이클 검출에 실패하게 됩니다.

isbidip 4년 전 2

100개의 도시가 순차적으로 100개의 경로로 사이클을 생성하는 경우 100*100*1000000 까지 값이 커질 수 있습니다.

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

문제

문제

출처

ICPC

답이 왜 long long type이 필요한지 모르겠어요 ㅜㅜ

kimeun0 6년 전 2

namhong2001 5년 전 0

isbidip 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말