Cod sursa(job #2205396)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 19 mai 2018 00:01:38
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
/// Dijkstra (N^2 + M)
#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cassert>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int N = 50001;
const int MAX_COST = 20000;
const int INF = (N-1) * MAX_COST;

struct node{
    int index;
    int dist = INF;
    bool node_has_been_checked = false;
};

class cmp{
    public:
        bool operator()(pair<int, int> A, pair<int, int> B){
            return A.first > B.first;
        }
};

vector<pair<int, int> > neighbours[N]; /// node_index, dist
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> nodeWarps; /// distance, node_index
node nodes[N];
int n,m;

bool check_new_node(){
    /// Eliminate visited nodes
    while(!nodeWarps.empty() && nodes[nodeWarps.top().second].node_has_been_checked == true){
        //cout<<"Popping warp "<<nodeWarps.top().second<<", d="<<nodeWarps.top().first<<"\n";
        nodeWarps.pop();
    }

    /// Assert
    if(nodeWarps.empty())
        return false;

    /// Warp
    pair<int, int> best_warp = nodeWarps.top();
    //cout<<"Visiting "<<best_warp.second<<", distance = "<<best_warp.first<<"\n";
    nodeWarps.pop();
    nodes[best_warp.second].node_has_been_checked = true;
    nodes[best_warp.second].dist = best_warp.first;

    /// Visit neighbours
    for(auto &neighbour : neighbours[best_warp.second])
        if(!nodes[neighbour.first].node_has_been_checked)
        {
            //cout<<"Adding warp "<<neighbour.first<<", d = "<<best_warp.first + neighbour.second<<"\n";
            nodeWarps.push({best_warp.first + neighbour.second, neighbour.first});
        }

    return true;
}

int main()
{
    /// Input
    freopen("dijkstra.out","w",stdout);
    in>>n>>m;
    for(int i=0; i<m; ++i){
        int from, to, dist;
        in>>from>>to>>dist;

        neighbours[from].push_back({to, dist});
    }

    //cout<<n<<" "<<m<<"\n"; for(int i=1; i<=n; ++i) {cout<<i<<": "; for(auto &x : neighbours[i]) cout<<"("<<x.first<<", "<<x.second<<") "; cout<<"\n";}

    /// Solve
    nodeWarps.push({0, 1});
    for(int i=1; i<=n; ++i)
        if(!check_new_node())
            break;

    /// Print
    for(int i=2; i<=n; ++i)
        cout<<(nodes[i].dist!=INF?(nodes[i].dist):0)<<" ";

    return 0;
}