Cod sursa(job #1207019)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 11 iulie 2014 19:37:46
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <set>
#include <utility>
#define mp make_pair
#define ff first
#define ss second
#define BIG 0x7fffffff
using namespace std;

int n,m;

vector< pair<int,int> > g[50001];

vector<int> dijkstra(int start) {
    vector <int> v(n+1,BIG);
    pair<int,int> node,cand;
    set< pair<int,int> > frontier;
    int i;

    node.ff=0;
    node.ss=start;
    v[start]=0;
    frontier.insert(node);

    while(!frontier.empty()) {
        node=*frontier.begin();
        frontier.erase(frontier.begin());

        for (i=0; i<g[node.ss].size(); i++)
            if (node.ff+g[node.ss][i].ff < v[g[node.ss][i].ss]) {
                cand.ff=node.ff + g[node.ss][i].ff;
                cand.ss=g[node.ss][i].ss;
                v[cand.ss]=cand.ff;
                frontier.insert(cand);
            }

    }

    return v;

}


int main() {
    int i,sn,en,val;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in>>n>>m;
    for (i=1; i<=m; i++) {
        in>>sn>>en>>val;
        g[sn].push_back(mp(val,en));
    }

    vector<int> dist=dijkstra(1);

    for (i=2; i<=n; i++)
        if (dist[i]==BIG)
            out<<0<<' ';
        else
            out<<dist[i]<<' ';

    out<<'\n';
    in.close();
    out.close();
    return 0;

}