글 읽기 - 그래서 출발점이 무조건 1이라는 건가요 어떤 노드든 상관 없다는 건가요?

ds04030 3년 전 1

게시글에 있는 질문글은 다 읽어보았고 반례도 통과합니다.

저는 플로이드 와샬 알고리즘으로 풀이하였습니다.

그런데 틀렸다고 나옵니다.

이 문제는 그래서 출발점이 무조건 1이라는 건지 X노드라는 건지 모르겠네요..

출발점이 1인가요 X인가요?

#include <iostream>
#include <vector>
#define NUM 501
#define INF 2000000000

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int TC, N ,M,W;
	cin >> TC;
	for(int tc=1; tc<=TC; tc++){
		bool checkAns = false;
		int arr[NUM][NUM];
		cin >> N >> M >> W;
		for(int i=1; i<=N; i++){
			for(int j=1; j<=N; j++){
				if(i==j) arr[i][j] = 0;
				else arr[i][j] = INF;
			}
		}

		int s,e,t;
		for(int i=0; i<M;i++){
			cin >> s >> e >> t;
			if(t < arr[s][e]) arr[s][e] = t;
			if(t < arr[e][s]) arr[e][s] = t;
		}

		for(int i=0; i<W;i++){
			cin >> s >> e >> t;
			if(-t < arr[s][e]) arr[s][e] = -t;
		}

		for(int k=1; k<=N; k++){
			for(int i=1; i<=N; i++){
				for(int j=1; j<=N; j++){
					if(arr[i][k] + arr[k][j] < arr[i][j]){
						arr[i][j] = arr[i][k] + arr[k][j];
					}
				}
			}
		} 

		for(int i=1; i<=N; i++){
			if(arr[i][i] < 0) {
				checkAns = true;
				break;
			}
		}

		if(checkAns) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}

	return 0;
}

shg9411 3년 전 1

어떤 점이든 상관 없습니다.

ds04030 3년 전 1

흠..

아래처럼 시작 노드를 1 (int start = 1)로 지정해주니 맞다고 뜨네요..

제가 36번째 줄처럼 1번 노트~N번째 노드까지 탐색하니까 시간초과가 뜨구요..

이거 문제를 그냥 시작노드는 1이라고 해야하는거 아닌가요?

지금 오타/요청을 할수가 없어서 누가 나중에 요청좀 해주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#define NUM 501
#define INF 2000000000
#define pii pair<int,int>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int TC;
	cin >> TC;
	for(int tc=1; tc<=TC; tc++){
		int N,M,W,s,e,t;
		vector<pii> v[NUM];
		int dist[NUM];
		cin >> N >> M >> W;
		for(int i=1; i<=N; i++) v[i].clear();

		while(M--){
			cin >> s >> e >> t;
			v[s].push_back(make_pair(e,t));
			v[e].push_back(make_pair(s,t));
		}
		while(W--){
			cin >> s >> e >> t;
			v[s].push_back(make_pair(e,-t));
		}

		//벨만포드 알고리즘
		bool ans = false;

		//for(int start=1; start<=N; start++){
		int start = 1;
		bool cycle = false;	
		for(int i=1; i<=N; i++) dist[i] = INF;
		dist[start] = 0;

		for(int i=1; i<=N; i++){
			for(int j=1; j<=N; j++){
				for(int p=0; p<v[j].size(); p++){
					int node = v[j][p].first;
					int val = v[j][p].second;
					if(dist[node] > val + dist[j]){
						dist[node] = dist[j] + val;
						if(i==N) cycle = true;
					}
				}
				if(cycle) break;
			}
			if(cycle) break;
		}
		if(cycle || dist[start] < 0) ans = true;
		//}

		if(ans) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}

	return 0;
}

shg9411 3년 전 1

전에 하셨던 질문이랑 일맥상통하지 않습니다.

출발점이 무조건 1이라는 건지 x노드라는 건지 물어보셨었고, 어느 점을 출발점으로 잡던 상관 없다고 말씀드렸습니다.

출발점을 어느 점으로 잡는지랑, 모든 정점에 대해서 계산하는 것이랑은 이 문제 기준으로 최대 500배 차이가 나겠죠.

ds04030 3년 전 0

출발점을 N으로 잡고 N개의 정점에 대하여 벨만포드를 풀어야 하는건지(벨만포드 알고리즘을 N번 수행)

출발점을 1로 잡고 N개의 정점에 대하여 벨만포드를 풀어야하는건지 궁금했습니다.(벨만포드 알고리즘을 1번 수행)

저는 전자라고 생각하였으나 후자가 맞았습니다..

pichulia 3년 전 2

게시판에 올려두신 코드는 시작점이 어디라도 상관없이 음수사이클이 있으면 yes를 출력하는 코드가 맞습니다.

dist값이 0이 아니라 INF에서 시작하는 음수사이클일 뿐이죠.

이 코드를 틀리게 만드는 데이터를 찾고있는데 쉽진 않네요ㅠ

ds04030 3년 전 0

제가 올린 두번째 코드가 시작점이 어디라도 상관없이 음수사이클이 있으면 yes를 출력하는 코드라고 말씀하시는거죠 ?

(제가 올린 두번째 코드를 아직 보지 않으셨다면, 봐주시면 감사하겠습니다^^ 두번째 코드로 통과하였습니다)

반례를 찾아주고 계신다니.. 정말 감사합니다. 다른분들에게도 많은 도움이 될것 같습니다.

pichulia 3년 전 1

조금 고민해봤는데 그냥 맞는 코드인거 같습니다.

그 증거로 dist[start]=0; 부분을 지워도 정답을 받습니다.

따라서 지문을 수정할 필요가 없습니다.

ds04030 3년 전 0

아 !! 결국은

시작점이 어디든간에 음수 싸이클만 있다는 것을 확인하면 "yes'" 라는 거군요?

그래서 dist[start]=0; 을 지워도 되는 것이구요..

또한 56번째줄에 if(cycle || dist[start] < 0) ans = true; 에서

dist[start]<0 조건을 뺀 if(cycle) 만 해도 정답처리가 되네요

감사합니다.

yhs05323 2년 전 1

저는 플로이드 워셜로만 풀린다고 생각했는데 벨만 포드로 가능한가보네요.

저는 1과 연결되어 있지 않은 노드가 있다면 그 노드의 음수 사이클을 벨만포드 알고리즘으로 발견 할 수 없다 생각했습니다. 이 생각이 틀린 건가요??

아 헷갈립니다. 공부가 많이 부족한가봐요..

cfhhtw15 5달 전 2

어느 곳에서 시작하는지 중요하지 않는 이유는 시작하는 점과 연결이 안된 곳도 갱신이 되기 때문이라고 생각합니다. 만약에 46번 줄 다음에

if(dist[j] == INF) continue;

라는 코드를 넣었다면 시작하는 점이 중요해지겠지만 위의 조건문이 없기 때문에 시작점과 연결이 안된 점도 갱신이 되고 있습니다.

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

문제

문제

출처

ICPC

그래서 출발점이 무조건 1이라는 건가요 어떤 노드든 상관 없다는 건가요?

ds04030 3년 전 1

shg9411 3년 전 1

ds04030 3년 전 1

shg9411 3년 전 1

ds04030 3년 전 0

pichulia 3년 전 2

ds04030 3년 전 0

pichulia 3년 전 1

ds04030 3년 전 0

yhs05323 2년 전 1

cfhhtw15 5달 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말