Problema "Super Marco 2 - ois_monete"

dp_1 · 13 Gennaio 2016, 4:22pm

Ciao a tutti!
Sto provando a risolvere il problema ois_monete, ma non riesco ad andare oltre il primo testcase. Premetto che l’algoritmo dovrebbe essere giusto, solo che anche provando vari casi di input da me inventati non riesco a trovare l’errore.
L’agoritmo che uso è abbastanza semplice: Eseguo una BFS partendo dalla piattaforma 0 e sommo tutte le monete che incontro

Ecco il codice che sto usando:

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;

typedef struct
{
    int coins;
    bool visited;
    vector<int> arcs;
} Platform;

Platform *platforms;

int main()
{
#ifndef TESTING
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    
    int N, M;
    scanf("%d %d", &N, &M);
    platforms = (Platform *)malloc(N * sizeof(Platform));
    
    for(int i = 0; i < N; i++)
    {
        platforms[i].arcs = vector<int>();
        scanf("%d", &platforms[i].coins);
        platforms[i].visited = false;
    }
    for(int i = 0; i < M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        platforms[a].arcs.push_back(b);
        platforms[b].arcs.push_back(a);
    }
    
    // BFS
    int total = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        platforms[node].visited = true;
        Platform p = platforms[node];
        
        total += p.coins;
        
        for(auto i = p.arcs.begin(); i != p.arcs.end(); ++i)
            if(platforms[*i].visited == false)
                q.push(*i);
    }
    
    printf("%d", total);
    free(platforms);
    
    return 0;
}

Dario

dp_1 · 13 Gennaio 2016, 4:32pm

Oops, risolto
Nella bfs segnavo come visitati i vertici dopo averli estratti dalla coda, e non quando li inserivo. In alcuni casi questo inseriva alcuni nodi più volte e quindi contava le loro monete più di una volta.

Ecco un testcase che riproduce l’errore, in caso servisse a qualcuno:

Dario