글 읽기 - SPFA 알고리즘에서 루프 체크관련 질문

kyy627 7년 전 0

SPFA 알고리즘에서

cnt를 얼마 이상으로 잡아야 하는지 잘 모르겠습니다.

제 생각에는 N개면 될 것 같은데 오답 처리 됩니다.

ㅜ.ㅜ

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int MAX_INT = 0x7fffffff;
int N, M;
vector<pair<int, int> > edge[6001];
int dist[501];
queue<pair<int, int> > q;
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		edge[a].push_back(make_pair(b, c));
	}

	for (int i = 1; i <= N; i++) {
		if (i == 1)
			dist[i] = 0;
		else
			dist[i] = MAX_INT;
	}
	q.push(make_pair(1, 0));

	int cnt = 10000;
	while(!q.empty() && --cnt) {
		int curNode = q.front().first;
		int curCost = q.front().second;
		q.pop();
		for (int i = 0; i < edge[curNode].size(); i++) {
			int nextNode = edge[curNode][i].first;
			int nextCost = edge[curNode][i].second;
			int result = curCost + nextCost;
			if (dist[curNode] != MAX_INT && dist[nextNode] > result) {
				dist[nextNode] = result;
				q.push(make_pair(nextNode, result));
			}
		}
	}

	if (cnt == 0)
		printf("-1\n");
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] == MAX_INT)
				printf("-1\n");
			else
				printf("%d\n", dist[i]);
		}
	}

	return 0;
}

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

문제

문제

출처

ICPC

SPFA 알고리즘에서 루프 체크관련 질문

kyy627 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말