글 읽기 - 어디가 틀린걸까요...

kth990303 3년 전 0

밸만포드 알고리즘 연습 겸 풀어보았습니다.

계속 틀렸다고 뜨는데, 어디가 문제일까요...

9%에서 틀렸다고 뜹니다

#include <iostream>
#include <vector>
using namespace std;
const int INF = 1000000000;
vector<pair<int, int>> v[701];
int n, m, w;
int d[701];
void getAns() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (auto cur : v[j]) {
				int e = cur.first;
				int cost = cur.second;
				if (d[j] != INF && d[e] > d[j] + cost) {
					d[e] = d[j] + cost;
					if (i == n) {
						cout << "YES\n";
						return;
					}
				}
			}
		}
	}

	cout << "NO\n";
	return;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m >> w;
		for (int i = 0; i < n + 1; i++)
			v[i].clear();
		fill(d, d + n + 1, INF);
		d[1] = 0;
		for (int i = 0; i < m; i++) {
			int a, b, cost;
			cin >> a >> b >> cost;
			v[a].push_back({ b, cost });
			v[b].push_back({ a, cost });
		}
		for (int i = 0; i < w; i++) {
			int a, b, cost;
			cin >> a >> b >> cost;
			v[a].push_back({ b, -cost });
		}
		getAns();
	}

}

kth990303 3년 전 2

https://www.acmicpc.net/board/view/50494 덕분에 14번째 줄의 d[j] != INF 없애고 통과했습니다.

낮에 d[j] != INF 없앤 코드로 제출하고 틀렸던 거 같은데, 다른 부분까지 잘못 수정했나봅니다..

중복인 듯한 느낌이 들지만 글삭은 비매너(?)니까 삭제는 안하겠습니다

qhsl1213 2년 전 0

저도 덕분에 해결했습니다 ㅎㅎ

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

문제

문제

출처

ICPC

어디가 틀린걸까요...

kth990303 3년 전 0

kth990303 3년 전 2

qhsl1213 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말