글 읽기 - [C++] 도와주세요 ㅠㅠ!

robin1001 7년 전 0

우선 저는 옮길 물건의 중량을 이분탐색으로 서칭하고 이 과정에서 물건의 중량(mid)이 옮길 수 있으면 (mid+1,b)의 범위 옮길 수 없으면 (a,mid-1)범위로 줄여서 탐색하는 식으로 문제를 풀었습니다. 어디서 틀렸는지 도저히 감이 잡히질 않아서 질문드립니다!

#include <cstdio>
#include <vector>
using namespace std;
int n,m;
int start,endp;
long ans,range=0;

typedef struct bridge{
  int e;
  long l;
}BRIDGE;

vector <BRIDGE> a[100001];
bool check[100001];

bool dfs(int node, long lim){
  check[node] =true;
  for(int i=0; i<a[node].size(); i++){
    int next = a[node][i].e;
    long bridgeLIM = a[node][i].l;
    if((next == endp)&&(bridgeLIM >= lim)) return true;
    if(!check[next] && (bridgeLIM >= lim))return dfs(next,lim);
  }
  return false;
}

void solve(long a, long b){
  if(a>b) return ;
  long mid = (a+b)/2;
  for(int i=0; i<100000; i++) check[i] = false;
  if(dfs(start,mid)){
    if(ans<mid)ans = mid;
    solve(mid+1,b);
  }
  else solve(a,mid-1);
  return ;
}

int main(){
  scanf("%d %d",&n,&m);
  for(int i=0; i<m; i++){
    int u,v; long c;
    scanf("%d %d %ld",&u,&v,&c);
    if(range<c) range = c;
    BRIDGE tmp1,tmp2;
    tmp1.e = v; tmp1.l = c;
    tmp2.e = u; tmp2.l = c;
    a[u].push_back(tmp1);
    a[v].push_back(tmp2);
  }
  scanf("%d %d",&start,&end[);
  solve(1,range);
  printf("%ld\n",ans);
  return 0;
}

cake_monotone 7년 전 0

dfs가 잘못 구현됐습니다

22 번째 줄

return dfs() 으로 하시면, 진행하다 false가 나와도 다음 노드를 탐색하지 못하고 줄줄히 false만 반환하고 끝나게 됩니다.

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

문제

문제

출처

ICPC

[C++] 도와주세요 ㅠㅠ!

robin1001 7년 전 0

cake_monotone 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말