글 읽기 - 반례나 오류 있을까요 ㅠㅠ 5%에서 틀립니다

jms020820 1년 전 0

st 시작 ed 도착

버스 비용을 음수로 버는 비용을 양수로 해서 최대 경로 구했습니다

1. ed 에 도착할 수 없으면 "gg"

2 . 사이클이 존재하지만 사이클에서 ed에 도착못하면 dist[ed]

3. 사이클이 존재하고 ed에 도착 할 수 있으면 "Gee"

4. 사이클이 없으면 dist[ed]

를 출력하도록 했습니다

알고리즘 오류나 반례있을까요 ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#define Next first
#define Cost second
#define ll long long
const ll INF = 2*1e18;
using namespace std;
typedef pair<int,int>P;
int st,ed;
ll dist[51];
int earn[51];
vector<int>cycle;
vector<P>graph[51];
void BellmanFord(int n);
int main(){
	int n,m,w;
	cin >> n >> st >> ed >> m;
	while(m--){
		int st_,ed_,cost;
		cin >> st_ >> ed_ >> cost;
		graph[st_].push_back({ed_,-cost});
	}
	for(w=0;w<n;w++)cin >> earn[w];
	BellmanFord(n);
	if(dist[ed]==-INF)cout << "gg\n";
	else if(cycle.size()>0){
		int count = 0;
		for(auto &w:cycle)
			for(auto &k:graph[w])
				if(k.Next==ed)count++;
		if(count==0)cout << dist[ed] << '\n';
		else cout << "Gee\n";
	}else cout << dist[ed] << '\n';
	return 0;
}
void BellmanFord(int n){
	fill(dist,dist+n+1,-INF);
	dist[st] = earn[st];
	for(int w=1;w<=n;w++)
		for(int e=0;e<n;e++)
			for(auto &k:graph[e])
				if(dist[e]!=-INF&&dist[k.Next]<dist[e]+k.Cost+earn[k.Next]){
					if(w==n)cycle.push_back(k.Next); 
					else dist[k.Next] = dist[e] + k.Cost + earn[k.Next];
				}
	return;
}

jms020820 1년 전 0

해결했습니다!!

저는 cycle 벡터에 사이클에 포함되는 정점들이 전부 들어간다고 생각했는데 전부 들어가지 않나보네요

사이클에 포함되는 정점하나만 큐에 넣고 BFS돌려서 ed에 도달하는지 탐색했습니다.

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

문제

문제

출처

ICPC

반례나 오류 있을까요 ㅠㅠ 5%에서 틀립니다

jms020820 1년 전 0

jms020820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말