글 읽기 - 플로이드-와샬로 풀이해보았습니다.

lcdoac12 3년 전 0

안녕하세요!

어디서 틀린 것인지 전혀 감이 잡히지 않아 글을 남기게 되었습니다.

플로이드-와샬 알고리즘이 음의 사이클이 없다면, 음의 가중치가 있어도 수치적으로 의미있는, 정상적인 결과를 내고

음의 사이클이 있다면, 수치적인 의미는 없지만 음의 사이클을 감지해낼 수 있다고 알고있습니다.

그래서 플로이드 와샬 알고리즘으로 최단경로를 저장한 2차원 벡터를 구하고,

대각선 요소들 중에 음수가 있다면 음의 사이클이 존재한다!

이런 생각으로 풀이했습니다.

그런데.. 틀립니다..ㅠㅠ

코드에서 틀린것인지, 제가 플로이드-와샬에 대해 잘못 이해하고 있는 것인지 피드백을 좀 받고 싶습니다..!

감사합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--) {
		int N, M, W;
		scanf("%d %d %d", &N, &M, &W);
		vector<vector<int>> gra(N, vector<int>(N, 123456789));

		while (M--)
		{
			int node1, node2, weight;
			scanf("%d %d %d", &node1, &node2, &weight);
			if (gra[node1 - 1][node2 - 1] < weight) continue;
			gra[node1 - 1][node2 - 1] = weight;
			gra[node2 - 1][node1 - 1] = weight;
		}
		while (W--)
		{
			int node1, node2, weight;
			scanf("%d %d %d", &node1, &node2, &weight);
			gra[node1 - 1][node2 - 1] = -weight;
		}

		for (int i = 0; i < N; i++) gra[i][i] = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					if (gra[j][k] > gra[j][i] + gra[i][k])
						gra[j][k] = gra[j][i] + gra[i][k];
		
		bool cycle_check = false;
		for (int i = 0; i < N; i++)
			if (gra[i][i] < 0) {
				printf("YES\n");
				cycle_check = true;
				break;
			}
		if (!cycle_check) printf("NO\n");
	}
	return 0;
}

bupjae 3년 전 1

P 에서 P로 향하는 웜홀이 존재할 때 계산이 잘못되었습니다.

입력:
1
2 1 1
1 2 2
2 2 3


정답:
YES

오답:
NO

lcdoac12 3년 전 0

헐 감사합니다..!!!!!!!

lcdoac12 3년 전 0

정말 감사합니다 ㅠㅠㅠㅠ

왜 start와 end가 항상 다를거라고 생각했는지...

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

문제

문제

출처

ICPC

플로이드-와샬로 풀이해보았습니다.

lcdoac12 3년 전 0

bupjae 3년 전 1

lcdoac12 3년 전 0

lcdoac12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말