Cod sursa(job #1435027)

Utilizator thebest001Neagu Rares Florian thebest001 Data 11 mai 2015 21:05:58
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <queue>

#define MAX_N 50001
#define INF 0x7fffffff
using namespace std;

int n, m;

struct lant {
    int nod_;
    int cost_;
    lant(int nod, int cost) : nod_(nod), cost_(cost) { }
};

vector<lant> graf[MAX_N];
bool viz[MAX_N];
int cost[MAX_N];
void solve();

int main() {

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int i;
    int x, y, c;

    for (i = 2; i <= n; i++) {
        cost[i] = INF;
    }

    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &c);
        graf[x].push_back(lant(y, c));
        graf[y].push_back(lant(x, c));
    }

    solve();

    for (i = 2; i <= n; i++)
        printf("%d ", cost[i]);
    printf("\n");

    return 0;
}

class comparator {
public:
bool operator() (const int &lh, const int &rh) const {
    return cost[lh] > cost[rh];
}
};

#ifdef XIO_DEBUG
#define log(x...) (printf(x),printf("\n"))
#else
#define log(x...) ;
#endif
void solve() {

    priority_queue<int, vector<int>, comparator> coada;
    vector<lant>::const_iterator i;
    log("dijkstra");
    coada.push(1);

    while (!coada.empty()) {
        int top = coada.top();
        coada.pop();
        log("pop nod: %d cost: %d", top, cost[top]);
        viz[top] = true;

        for (i = graf[top].begin(); i != graf[top].end(); ++i) {
            if (viz[i->nod_])
                continue;
            log("    %d + %d < %d (nod: %d)", cost[top], i->cost_, cost[i->cost_], i->nod_);
            if (cost[top] + i->cost_ < cost[i->nod_]) {
                cost[i->nod_] = cost[top] + i->cost_;
                coada.push(i->nod_);
            }
        }
    }
}