글 읽기 - [C++] 웜홀 왜틀린지 모르겠습니다.

leejh3907 3년 전 0

밸만포드 알고리즘을 이용했습니다.

음의 사이클 존재 또는 출발노드의 값이 음수가 되었을경우 Yes를 출력하게 했습니다.

어떻게된건지 계속 오답이 나오더군요...

어떤 반례가 있는지, 어느부분에서 실수를 한것인지 모르겠습니다. 도와주실수 있을까요?

#include <iostream>
#include <vector>

#define endl "\n"
#define pure =0
#define INF 987654321

using namespace std;

int main()
{
	int t;
	cin>>t;
	
	while(t--)
	{
		int a, b, c;
		cin>>a>>b>>c;
		vector<vector<pair<int, int>>> v(a+1);
		vector<int> dist(a+1, INF);

		for(int i=0; i<b; i++)
		{
			int s, e, t;
			cin>>s>>e>>t;
			v[s].push_back({e, t});
		}

		for(int i=0; i<c; i++)
		{
			int s, e, t;
			cin>>s>>e>>t;
			v[s].push_back({e, -t});
		}

		bool cycle=false;
		dist[1]=0;

		for(int i=1; i<=a; i++)
		{
			for(int j=1; j<=a; j++)
			{
				for(int k=0; k<v[j].size(); k++)
				{
					int next=v[j][k].first;
					int d=v[j][k].second;
					
					if(dist[next]>dist[j]+d)
					{
						dist[next]=dist[j]+d;
						
						if(i==a) cycle=true;
					}
				}
			}
		}
		
		//for(int i=1; i<=a; i++) cout<<(dist[i]!=INF? dist[i]:-1)<<' ';

		if(cycle || dist[1]<0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

tizm423 3년 전 0

위 코드로는 음수사이클의 존재를 알 수 없습니다.

leejh3907 3년 전 3

if(dist[next]>dist[j]+d)

{

dist[next]=dist[j]+d;

if(i==a) cycle=true; //마지막 루프에 값이 갱신된다면 음의 사이클이 존재한다고 판단.

}

입력을 받을때 단방향으로 노드를 연결하니 틀렸습니다가 나왔었네요..

v[s].push_back({e, t});뒤에

v[e].push_back({s, t});를 추가해 양방향으로 만들어주니 맞았습니다가 나왔습니다.

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

문제

문제

출처

ICPC

[C++] 웜홀 왜틀린지 모르겠습니다.

leejh3907 3년 전 0

tizm423 3년 전 0

leejh3907 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말