글 읽기 - 타임머신 SPFA

nakgee 3년 전 0

세 번째 재채점으로 저의 코드는 나락으로....

1. 일단 출력초과 문제가 발생하는 이유가 음의 사이클이 생기는 경우 -1출력이 되지 않고 n-1개의 수를 출력하기 떄문인 것 같은데, 다음의 코드가 왜 음의 사이클을 모두 체크하지 못하는지 궁금합니다. 문제에서 1번정점에서 출발해서 음의 사이클을 체크 하라 했으니 SPFA를 써도 무방하다고 생각합니다.

2. 같은 정점 사이의 거리에서 최소값만 리스트에 넣는 것이 맞다고 생각합니다.( 지난번 재채점시 이것을 수정해서 다시 AC를 받았습니다.)

이 두가지를 수정하여 두번의 재채점을 통과했는데 다시 재채점되어 틀렸습니다를 보니 슬퍼만집니다.... 어떤 문제가 있을까요.?

반례혹은 제가 잘못생각한 부분을 알려주세요 !

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

#define N 550
#define INF 99999999
typedef pair<int, int> pii;


int r[N][N];
int n, m;
vector<pii> v[N];
int dis[N],cycle[N],chk[N];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			r[i][j] = INF;
		}
	}
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		r[a][b] = min(r[a][b], c); // 최소 간선으로 리스트에 추가
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (r[i][j] != INF) v[i].push_back({ j,r[i][j] });// 최소 간선으로 리스트에 추가
		}
	}
	for (int i = 1; i <= n; i++) dis[i] = INF;

	queue<int> q;
	q.push(1);
	dis[1] = 0;
	cycle[1] ++;
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		chk[here] = false;
		for (auto next : v[here]) {
			if (dis[here] + next.second < dis[next.first]) {
				dis[next.first] = dis[here] + next.second;
				if (!chk[next.first]) {
					cycle[next.first]++;
					if (cycle[next.first] >= n) {
						cout << -1;
						return 0;
					}
					q.push(next.first);
					chk[next.first] = true;
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (dis[i] == INF)cout << "-1\n";
		else cout << dis[i] << "\n";
	}

	return 0;
}

sait2000 3년 전 3

https://www.acmicpc.net/board/...

반례는 여기 있습니다.

그래프가 대략 아래처럼 생겼는데, 질문자님 코드는 아래 그래프에서 500바퀴를 돌기 전에 거리가 음의 방향으로 오버플로우가 납니다.

1 --(-10000)--> 2 --(-10000)--> ... --(-10000)--> 500
^                                                  |
 \-------------------(-10000)---------------------/

nakgee 3년 전 1

오버플로우를 생각하지 못했네요.... 정말 감사합니다

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

문제

문제

출처

ICPC

타임머신 SPFA

nakgee 3년 전 0

sait2000 3년 전 3

nakgee 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말