글 읽기 - 11%에서 틀리는데 이유를 모르겠네요..ㅠㅠ

wiz9243 6년 전 0

1번에서 출발한다했으니까 1번을 시작노드로 놓고, 베르만포드를 돌렸는데 음수사이클이 존재하면 맞는거 아닌가요?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;
#define MAX 10000005
struct edge {
	int start, end, cost;
};
vector<edge> v;
int dist[505];

int main() {
	int T; cin >> T;
	while ( T-- ) {
		int n, m, w; scanf("%d %d %d", &n, &m, &w);
		v.clear();
		for ( int i = 1; i <= n; i++ ) dist[i] = MAX;
		dist[1] = 0;

		for ( int i = 0; i < m; i++ ) {
			int a, b, c; scanf("%d %d %d", &a, &b, &c);
			v.push_back({ a,b,c });
			v.push_back({ b,a,c });
		}
		for ( int i = 0; i < w; i++ ) {
			int a, b, c; scanf("%d %d %d", &a, &b, &c);
			v.push_back({ a,b,-c });
			v.push_back({ b,a,-c });
		}


		bool flag = false;

		for ( int i = 1; i <= n; i++ ) {
			for ( int j = 0; j < m * 2 + w; j++ ) {
				int now = v[j].start;
				int dest = v[j].end;
				int D = v[j].cost;

				if ( dist[now]!=MAX && dist[dest] > dist[now] + D ) {
					dist[dest] = dist[now] + D;
					if ( i == n ) {
						flag = true;
						break;
					}
				}
			}
		}
		if ( flag )cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

Green55 6년 전 0

1
3 2 2
1 2 1
2 1 1
3 4 1
4 3 1

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

문제

문제

출처

ICPC

11%에서 틀리는데 이유를 모르겠네요..ㅠㅠ

wiz9243 6년 전 0

Green55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말