글 읽기 - 반례좀 부탁드리겠습니다... 윽

jinsik 3년 전 2

본문의 예제는 통과하고, 반례를 좀 찾아보다가

10
7 6
9
1 2
1 3
1 4
9 1
9 10
3 5
3 6
2 7
2 8

expected: 4
output: 5

이렇게 돼서 bool all_visited를 만들어 고쳤습니다.

그런데도 똑같은 지점에서 틀려서 질문드립니다 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int visited[101], ans;
vector<int> graph[101];

int main() {
    int p; cin >> p;
    int begin, end;
    cin >> begin >> end;
    int m; cin >> m;

    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    bool escape = false;
    queue<int> q;
    q.push(begin);
    visited[begin] = 1;
    while(!q.empty()) {
        int n = q.front();
        q.pop();
        ans++;

        bool all_visited = true;
        for(auto next: graph[n]) {
            if(visited[next]) continue;
            if(next == end) {
                cout << ans;
                escape = true;
            }
            all_visited = false;
            q.push(next);
            visited[next] = 1;
        }
        if(all_visited) ans--;
        if(escape) break;
    }
    if(!visited[end]) cout << -1;
    else if(begin == end) cout << 0;

    return 0;
}

djm03178 3년 전 6

아래와 같은 입력이 반례입니다.

jinsik 3년 전 0

정말 감사합니다...

그냥 탐색하면서 ans++ 하는것보다 end까지 가는 거리를 생각해서 풀었어요!

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

문제

문제

출처

ICPC

반례좀 부탁드리겠습니다... 윽

jinsik 3년 전 2

djm03178 3년 전 6

jinsik 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말