글 읽기 - 이 문제 벨만포드로 통과되는 이유가 무엇인가요??

yeongjae8066 4년 전 0

벨만포드는 모든 간선에 대해서 정점의 개수만큼(V-1) 검사해야 해서 O(E*V)로 1억에 해당하는 숫자라서 0.5초로 막아놓은 것 같다고 느껴서 한 번 벨만포드로 해봤는데 다익스트라 2배의 시간안에 통과가 되네요. 혹시 왜 그런지 알 수 있나요?

#include <vector>
#include <iostream>

using namespace std;

struct edge {
	int from, to, cost;
	edge() : from(0), to(0), cost(0) {}
	edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
};

vector<edge> a;
int dist[1001];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	a.resize(m);
	for (int i = 0; i < m; i++) {
		int x, y, d;
		cin >> x >> y >> d;
		a[i] = edge(x, y, d);
	}
	int inf = 2100000000;
	for (int i = 1; i <= n; i++) {
		dist[i] = inf;
	}

	int st, ex;
	cin >> st >> ex;
	dist[st] = 0;

	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) {
			int from = a[j].from;
			int to = a[j].to;
			int cost = a[j].cost;
			if (dist[from] != inf && dist[to] > dist[from] + cost) {
				dist[to] = dist[from] + cost;
			}
		}
	}

	cout << dist[ex] << '\n';
	return 0;
}

djm03178 4년 전 1

1억은 요즘 컴퓨터에서 1초 안에 넉넉하게 됩니다.

간단한 문장이라면 10억 번 이상도 실행할 수 있습니다.

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

문제

문제

출처

ICPC

이 문제 벨만포드로 통과되는 이유가 무엇인가요??

yeongjae8066 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말