Cod sursa(job #1705377)

Utilizator criss001CBanat criss001 Data 20 mai 2016 14:36:26
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <algorithm>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits>

enum GType { DIRECTED, UNDIRECTED };
typedef unsigned int NodeData;


long long bfs(unsigned int N, unsigned int init_node, unsigned dest_node, std::vector<std::list<unsigned int> > &adj) {

    if (init_node == dest_node) return 0;
    if (init_node > N) return -1;

    // BFS
    unsigned int curr_node;
    long long distance = 0;
    bool visited[N + 1];
    std::memset(visited, false, N+1);
    long long cost[N + 1];
    std::memset(cost, 0, sizeof(long long) * (N+1));


    std::queue<unsigned int> q;

    // Adaug nodul initial
    q.push(init_node);
    visited[init_node] = true;

    while (!q.empty()) {

        curr_node = q.front(); q.pop();
        if (curr_node == dest_node) return distance;

        for (std::list<unsigned int>::iterator neigh = adj[curr_node].begin(); neigh != adj[curr_node].end(); neigh++) {
            if (!visited[*neigh]) {
                q.push(*neigh);
                visited[*neigh] = true;
                cost[*neigh] = cost[curr_node] + 1;
                if (*neigh == dest_node) return cost[*neigh];
            }
        }

    }

    return -1;
}

int main(int argc, char **argv) {

    std::ifstream input("bfs.in");

    if (!input.is_open()) {
        std::cerr << "Cannot open input file!" << std::endl;
        std::exit(-1);
    }

    std::ofstream output("bfs.out");

    if (!output.is_open()) {
        std::cerr << "Cannot open output file!" << std::endl;
        input.close();
        std::exit(-2);
    }

    // Citire Graph
    GType gtype = DIRECTED; // orientat / neorientat
    unsigned int N, M, u, v, dest_node;
    input >> N >> M >> dest_node;

    NodeData nodes[N + 1];
    std::vector<std::list<unsigned int> > adj(N + 1, std::list<unsigned int>());

    while(input >> u >> v) {
        if (u == v) continue;
        adj[u].push_back(v);
        if (gtype == UNDIRECTED) adj[v].push_back(u);
    }

    for (int i = 1; i <= N; i++)
    std::cout << bfs(N, i, dest_node, adj) << std::endl;

    input.close();
    output.close();

    return 0;
}