Water park (waterslide) - aiuto

Aiuto
1

Ciao, di recente ho cominciato ad imparare le tecniche di base per risolvere problemi con i grafi. Per adesso sono riuscito a completare sentieri, licenziamenti, ponti, monete, ciclismo, dessert e trip.

Quali altri problemi, di circa questo livello, mi consigliate di provare?

Per adesso sono fermo su waterslide a 45/100 perché tre subtests vanno fuori tempo. Questo è il codice:

#include <bits/stdc++.h>

int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");

    std::ios::sync_with_stdio(false);
    ifs.tie(0);

    int N = 0, M = 0, P = 0;
    ifs >> N >> M >> P;

    std::list<int> junctions[N];

    for(int i = 0, A, B; i < M; ++i){
        ifs >> A >> B;
        junctions[A].push_back(B);
    }

    std::vector<long double> pools(N, 0.0);

    std::unordered_map<int, long double> q;
    q.insert(std::make_pair(0, 1.0));
    while(!q.empty()){
        auto n = q.begin();

        if(junctions[n->first].size() == 0){
            pools[n->first] += n->second;
        }

        for(const auto& next : junctions[n->first]){
            q[next] += n->second / (long double) junctions[n->first].size();
        }

        q.erase(n);
    }

    auto ret = std::max_element(pools.cbegin(), pools.cend());

    ofs << ret - pools.cbegin();

    return 0;
}
2

Edit:

Dopo aver riscritto il programma usando una priority_queue di struct, la situazione è rimasta all’incirca la stessa.

#include <bits/stdc++.h>

struct Pair
{
    Pair(int i, long double x) :
        I(i), X(x) { }

    int I;
    long double X;
};

bool operator<(const Pair& lhs, const Pair& rhs){
    return (lhs.X > rhs.X);
}

int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");

    std::ios::sync_with_stdio(false);
    ifs.tie(0);

    int N = 0, M = 0, P = 0;
    ifs >> N >> M >> P;

    std::list<int> junctions[N];

    for(int i = 0, A, B; i < M; ++i){
        ifs >> A >> B;
        junctions[A].push_back(B);
    }

    std::vector<long double> pools(N, 1.0);

    std::priority_queue<Pair> q;
    q.emplace(0, 1.0);
    while(!q.empty()){
        Pair n = q.top();
        q.pop();

        if(n.X < 0.0001) continue;

        if(junctions[n.I].size() == 0){
            pools[n.I] += n.X;
        }

        for(const auto& next : junctions[n.I]){
            q.emplace(next, n.X / (long double) junctions[n.I].size());
        }

    }

    auto ret = std::max_element(pools.cbegin(), pools.cend());

    ofs << ret - pools.cbegin();

    return 0;
}

Poi però ho aggiunto quel (poco onesto)

if(n.X < 0.0001) continue;

e ho totalizzato 100. Opinioni in merito?

3

Ciao!
Non capisco bene il motivo della priority queue, qui non si tratta di far andare Dijkstra o cose simili, tuttavia il grafo è un DAG (in quanto non può esistere uno scivolo alla Escher :new_moon_with_face:) e quindi la cosa più logica è quella di visitare i nodi secondo il suo topological sort.