글 읽기 - dfs진행에 있어서

johyesong8686 3년 전 0

1번은 맞고

2번은 틀렸습니다.

둘다 go함수의 return 값이 true 이면 종료하고 아니면, 끝날때 까지 탐색하게 진행했는데

왜 2 번에서는 시간 초과가 날까요 ?

////1

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector <pair <int, long long >> node[100005];
int visited[100005];
int arrive;
int depart;

bool go(int cur,int mid) {
   
    visited[cur]=1;
	if(cur==depart) {
	   return true;
	}
	for (int i=0; i<node[cur].size();i++) {
		int next=node[cur][i].first;
		long long value=node[cur][i].second;
	    if(value<mid||visited[next]){
	        continue;
	    }else{
	        if(go(next,mid)){
			    return true;
			}else{
			    continue;
			}
	    }
	
	}
	return false;
	
}
int main() {
	int n,m;
	cin >>n >>m;
	long long  max_value=0;
	for (int i=0; i<m;i++) {
		int x,y;
		long long z;
		cin >>x >>y >>z;
		node[x].push_back(make_pair(y,z));
		node[y].push_back(make_pair(x,z));
		max_value=max(max_value,z);
	}
	cin >>arrive >>depart;
	long long end=max_value;
	long long start=1;
	long long ans=0;
	while(start <=end) {
		long long mid=(start+end)/2;
		memset(visited,0,sizeof(visited));
		visited[arrive]=1;
		int cur=arrive;
	
		bool result= go(cur,mid);
        if(result){
            ans=max(mid,ans);
            	start=mid+1;
            
        }

		 else {
			end=mid-1;
		}
	}
	cout <<ans <<'\n';
	return 0;
}

//////2

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector <pair <int, long long >> node[100005];
int visited[100005];
int arrive;
int depart;

bool go(int cur,long long mid) {
	if(cur==depart) {
	   return true;
	}
	for (int i=0; i<node[cur].size();i++) {
		int next=node[cur][i].first;
		long long value=node[cur][i].second;
	    if(value<mid){
	        continue;
	    }
		if(visited[next]==0) {
			visited[next]=1;
			if(go(next,mid)){
			    return true;
			}
			visited[next]=0;
			
		}
	}
	return false;
	
}
int main() {
	int n,m;
	cin >>n >>m;
	long long  max_value=0;
	for (int i=0; i<m;i++) {
		int x,y;
		long long z;
		cin >>x >>y >>z;
		node[x].push_back(make_pair(y,z));
		node[y].push_back(make_pair(x,z));
		max_value=max(max_value,z);
	}
	cin >>arrive >>depart;
	long long end=max_value;
	long long start=1;
	long long ans=0;
	
	while(start <=end) {
		long long mid=(start+end)/2;
		memset(visited,0,sizeof(visited));
		visited[arrive]=1;
		int cur=arrive;
		bool result= go(cur,mid);
		if(result) {
			ans=max(mid,ans);
			start=mid+1;
		} else {
			end=mid-1;
		}
	}
	cout <<ans <<'\n';
	return 0;
}

johyesong8686 3년 전 0

해결했습니다 ! 1번은 dfs인데 2번은 부르트 포스트 인 것 같습니다!

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

문제

문제

출처

ICPC

dfs진행에 있어서

johyesong8686 3년 전 0

johyesong8686 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말