ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 2034. Корованы

WA 32 ...why this method is wrong
Послано Sagar Goyal 8 авг 2022 14:41
Out of all shortest path I am finding min of maximum distance I have to travel for every level.





#include<bits/stdc++.h>
using namespace std;

void bfs(int u,vector<int> &d,const vector<vector<int>> adj){
    d[u] = 0;
    queue<int> q;
    q.push(u);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto v:adj[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n);

    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }

    vector<int> ds(n,1e9),df(n,1e9),dr(n,1e9);
    int s,f,r;
    cin>>s>>f>>r;
    s--,f--,r--;
    bfs(s,ds,adj);
    bfs(f,df,adj);
    bfs(r,dr,adj);

    vector<vector<int>> l(ds[f]+1);

    for(int i=0;i<n;i++){
        if(ds[i]+df[i]==ds[f]){
            l[ds[i]].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=ds[f];i++){
        int a = INT_MIN;
        for(auto x: l[i]){
            a = max(a,dr[x]);
        }
        ans = min(a,ans);
    }

    cout<<ans;

    return 0;
}
Re: WA 32 ...why this method is wrong
Послано AmEr 17 авг 2022 04:41
This is wrong because you're assuming that the answer is the minimum distance to the robbers in its unique optimal path, which is not always true.

Edited by author 17.08.2022 04:41

Edited by author 17.08.2022 04:41