글 읽기 - 1865번 반례 부탁드립니다!!

dldnsgml7 2년 전 0

올려주신 질문들 보면서 계속 수정해보았는데 초기화에서도 문제가 없는 것 같습니다. 음의 사이클은 마지막 완화에서 발생하므로 조건문 추가해서 돌려보는데도 계속 틀렸다고 나오네요ㅜㅠ 반례 보내주시면 감사하겠습니다!!

// 백준 1865 : 벨만 포드 맛보기
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;
const int INF=987654321;
int TC, N, M, W, S, E, T;;
vector<pair<int, int>> adj[501];
bool impossible;
string str[5];

void bellmanford(int N,int start) {
	vector<int> upper(N + 1, INF);
	upper[start] = 0;
	bool updated = false;

	for (int it = 1; it <= N; it++) {
		for (int here = 1; here <= N; here++) {
			for (int i = 0; i < adj[here].size(); i++) {
				int there = adj[here][i].first;
				int cost = adj[here][i].second;

				if (upper[there] > upper[here] + cost) {
					upper[there] = upper[here] + cost;
					if(it == N) updated = true;
				}
			}
		}
	}
	if (updated) impossible = false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> TC;
	for (int i = 0; i < TC; i++) {
		impossible = true;
		adj->clear();
		cin >> N >> M >> W;
		for (int j = 0; j < M; j++) {
			cin >> S >> E >> T;
			adj[S].push_back({E,T});
			adj[E].push_back({S,T});
		}
		for (int j = 0; j < W; j++) {
			cin >> S >> E >> T;
			adj[S].push_back({E,-T});
		}

		bellmanford(N, 1);

		if (!impossible) {
			str[i] = "YES";
		}
		else {
			str[i] = "NO";
		}
	}
	for (auto i : str) {
		cout << i << "\n";
	}
}

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

문제

문제

출처

ICPC

1865번 반례 부탁드립니다!!

dldnsgml7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말