글 읽기 - dfs로 풀었는데 반례가 뭔지 모르겠어요..ㅠㅠ

howdy90 7년 전 0

혹시 만들어 놓은 거 있으시면 좀 알 수 있을까요??

#include<stdio.h>
#include<vector>
 
using namespace std;
 
int N,M;
 
vector<int> bridge[10001];
vector<int> size[10001];
 
int dfs(int b);
int result = 0;
int result2 = 0;
int start,fin;
int check[10001];
int value[10001];
 
int main()
{
    scanf("%d %d",&N,&M);
     
    for(int i=0; i<M; i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        bridge[a].push_back(b);
        bridge[b].push_back(a);
        size[a].push_back(c);
        size[b].push_back(c);
    }
    scanf("%d %d",&start,&fin);
 
    int temp = 0;
	int tp = 0;
 
    for(int i=0; i<bridge[start].size(); i++)
    {
        check[start] = 1;
        result = size[start][i];
        if(result>temp)
        {
			tp = dfs(bridge[start][i]);
			if(tp>temp&&tp<=result)
				temp = tp;
			else if(tp>temp)
				temp = result;
		}
    }
    printf("%d\n",temp);
 
    return 0;
}
 
int dfs(int b)
{
    if(b==fin)
    {
        return result;
    }
    if(value[b]!=0)
        return value[b];
    check[b] = 1;
    int temp = 0;
	int tp = 0;
	int temp2 = 0;
    int change = 0;
	int cur = result;
    for(int i=0; i<bridge[b].size(); i++)
    {
		result = cur;
        if(check[bridge[b][i]]==0)
        {
            if(result>=size[b][i])
            {
                result = size[b][i];
            }
            else
            {
                change = 1;
            }
            if(result>temp)
            {
				tp = dfs(bridge[b][i]);
				if(tp>temp&&tp<=result)
					temp = tp;
				else if(tp>temp)
					temp = result;
			}
			if(change==1)
			{
				result = size[b][i];
				tp = dfs(bridge[b][i]);
				if(tp>temp2&&tp<=result)
					temp2 = tp;
				else if(tp>temp2)
					temp2 = result;
			}
        }
    }
    check[b] = 0;
	if(temp>temp2)
	    value[b] = temp;
	else
		value[b] = temp2;

	return temp;
}

badcandy 7년 전 3

9 9

1 4 11

1 5 2

4 5 4

4 3 10

4 2 7

5 2 10

5 6 13

3 2 9

2 6 8

1 6

넣어보세요

답은 9가 나와야됩니다.

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

문제

문제

출처

ICPC

dfs로 풀었는데 반례가 뭔지 모르겠어요..ㅠㅠ

howdy90 7년 전 0

badcandy 7년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말