글 읽기 - [c++] 반례가 필요합니다!

sos0911 4년 전 0

bfs로 접근을 시도했고

queue의 상태 공간에는 tuple=(현재 노드, 누적된 이동시간, 누적된 택시비)가 들어갑니다.

visited 벡터에 초기값=가진 돈+1로 설정해서 강의까지 남은 시간보다 tuple의 누적된 이동시간이 적거나 같고 visited에 저장된 돈보다 tuple의 누적된 택시비가 적을 경우 큐에 들어가게 했습니다.

뭐가 틀린 걸까요..??

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;
int n,maxt,maxm,l;
int bfs(vector<vector<tuple<int,int,int>>>& rel){
	queue<tuple<int,int,int>> bfsq; // 현재 노드, 지금까지 쌓인 이동시간, 택시비
	vector<int> visited(n+1, maxm+1);
	// 상한선 이동시간, 택시비
	// 현재 visited에 있는 수치보다 낮으면 통과
	bfsq.push(make_tuple(1,0,0));
	// 도중에 예산 초과 시 stop
	while(!bfsq.empty()){
		auto& temp=bfsq.front();
		bfsq.pop();
		for(auto& t:rel[get<0>(temp)])
			if(get<1>(temp)+get<1>(t)<=maxt && get<2>(temp)+get<2>(t)<visited[get<0>(t)]){
				// 수치보다 낮음
				bfsq.push(make_tuple(get<0>(t),get<1>(temp)+get<1>(t),get<2>(temp)+get<2>(t)));
				visited[get<0>(t)]=get<2>(temp)+get<2>(t);
			}
	}
	if(visited[n]==maxm+1) // 갱신x => 불가능
		return -1;
	else
		return visited[n];
}
int main(){
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin>>n>>maxt>>maxm>>l;
	vector<vector<tuple<int,int,int>>> rel; // 각 노드마다 길 정보 저장
	// 길 정보 : 목적지 이동시간(move) 택시비
	rel.reserve(n+1); // 0-
	for(int i=0;i<n+1;i++)
	rel.push_back(vector<tuple<int,int,int>>()); 
	int a,b,t,m;
	for(int i=0;i<l;i++){
		cin>>a>>b>>t>>m;
		rel[a].push_back(make_tuple(b,t,m));
		rel[b].push_back(make_tuple(a,t,m));
	}
	cout<<bfs(rel)<<'\n';
	return 0;
}

lokilo 4년 전 3

5
150 1000
5
1 2 50 240
1 3 25 250
2 4 50 240
3 4 25 250
4 5 100 50

lokilo 4년 전 1

아 추가적인 여담입니다만, 업로드 하신 소스를 제가 VS 2017 에서 돌렸을 때 BFS탐색하는 부분에서 temp값이 주소값이 건드려져서 인지 어떠한 이유인지는 모르겠으나 가끔 값이 변경되는 경우도 관측이 되었습니다. 제가 언어적인 부분은 잘 몰라서 정확한 답변은 못 드립니다 ;ㅅ;

sos0911 4년 전 0

와 진짜 감사합니다!

친절한 설명과 그림에 한번 더 감탄하고 갑니다.

생각해 보니까 저런 경우가 있었네요.

visited에 시간/cost 둘 다 저장해서 둘 중 하나라도 이득이면 지나가게 하는 게 맞는 것 같습니다.

temp값 변경은 c++ 초보라 잘 모르겠지만 auto&로 참조한 다음 그걸 pop 해버려서 그런 것 같습니다.

다시 한번 감사합니다!!

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

문제

문제

출처

ICPC

[c++] 반례가 필요합니다!

sos0911 4년 전 0

lokilo 4년 전 3

lokilo 4년 전 1

sos0911 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말