글 읽기 - 벨만포드 오답받으신분들 혹시나해서 참고하실거 주석달아놓음

gon109 4년 전 2

벨만포드 오답받으신분들 혹시나해서 참고하실거 주석달아놓음

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<cmath>
#include<functional>
using namespace std;
#define ll long long
#define pii pair<int,int> 
#define INF 987654321



int djikstra[20001];
vector<pii> adj[20001];


int main(void) {
	int V, E;

	cin >> V >> E;

	for (int i = 0; i < E; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		adj[a].push_back({ cost,b });

	}

	for (int i = 2; i <= V; i++) {
		djikstra[i] = INF;
	}
	bool cycle = false;
	for (int cnt = 1; cnt <= V; cnt++) {
		for (int here = 1; here <= V; here++) {
			//이 부분 때문에 처음에 오답받았어요
			//현재까지 경로가 존재하지 않는데 연산하는 경우 조심합시다
			if (djikstra[here] == INF) continue;
			for (auto &p : adj[here]) {
				int next = p.second;
				int dist = p.first;
				if (djikstra[next] > djikstra[here] + dist) {
					djikstra[next] = djikstra[here] + dist;
					if (cnt == V) {
						cycle = true;
					}
				}
			}
		}
	}
	if (cycle) {
		cout << -1;
	}
	else {

		for (int i = 2; i <= V;  i++) {
			if (djikstra[i] == INF)
				cout << -1<<"\n";
			else
				cout << djikstra[i] << "\n";
		}
	}

	return 0;
}

ploffer11 4년 전 3

dijkstra입니다

pikkoro97 4년 전 0

저도 같은 실수로 헤맸어요 시작점과 이어지지 않은 곳에 있는 negative cycle은 넘어가야 했는데 그걸 몰랐네요

jsjsjs0775 3년 전 0

데이터 추가되서 이거 제출하면 출력초과 뜨네요

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

문제

문제

출처

ICPC

벨만포드 오답받으신분들 혹시나해서 참고하실거 주석달아놓음

gon109 4년 전 2

ploffer11 4년 전 3

pikkoro97 4년 전 0

jsjsjs0775 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말