글 읽기 - 모든 정점에 대해서 조사하는게 아닌가요?

shinbian11 3년 전 0

어떤 부분이 틀렸는지 궁금하네요 ㅠ

#include <bits/stdc++.h>

// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

struct Edge
{
	int from, to, cost;
};

ll d[504]; //d[i] : i번째 도시에 도착하는 최단 시간

void solve()
{
	int n, m, w;
	cin >> n >> m >> w;

	vector<Edge> v(m+w);
	
	for (int i = 0; i < m; i++)
	{
		cin >> v[i].from >> v[i].to >> v[i].cost;
	}
	for (int i = m; i < m + w; i++)
	{
		cin >> v[i].from >> v[i].to >>  v[i].cost;
		v[i].cost *= (-1);
	}
	
	for (int i = 1; i <= n; i++)
		d[i] = 1e9;

	d[1] = 0;

	bool negative = false;

	for (int vertex = 1; vertex <= n; vertex++) // 모든 정점에 대해서, 그 정점에서 시작했을 때 음의 사이클이 존재하는지 확인하기 위해서 vertex 를 for문으로 돌림
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				int x = v[j].from;
				int y = v[j].to;
				int cost = v[j].cost;

				if (d[y] > d[x] + cost)
				{
					d[y] = d[x] + cost;

					if (vertex == n)  //if(i == n)으로 해도 안되네요..
					{
						negative = true;
					}
				}
			}
		}
	}

	if (negative)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';

	return;
}

int main()
{
	F_I;

	//[백준] 1865번 : 웜홀 (벨만포드)

	//음의 사이클이 존재하는지 물어보는 문제

	int tc;
	cin >> tc;
	while (tc--)
		solve();

	return 0;
}

shinbian11 3년 전 1

아.. 양방향으로 입력을 넣어야 하는군요! 자잘자잘한 부분에서 많이 틀렸네요 ㅠ 어쨌든 해결했습니다.

도움 받은 링크 : https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

모든 정점에 대해서 조사하는게 아닌가요?

shinbian11 3년 전 0

shinbian11 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말