Cod sursa(job #2422553)

Utilizator urweakurweak urweak Data 19 mai 2019 10:15:27
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>
#define pb push_back
#define LMAX 36125
using namespace std;
typedef pair<int, int> PII;
int N, M, K, is_catun[LMAX], f[LMAX], D[LMAX];
vector <PII> E[LMAX];
priority_queue<PII, vector<PII>, greater<PII>> Q;

void Dijkstra()
{
    while(!Q.empty())
    {
        int len = Q.top().first, nod = Q.top().second;
        Q.pop();
        if(len != D[nod])
            continue;
        for(auto it : E[nod])
            if(len + it.second < D[it.first])
            {
                D[it.first] = len + it.second;
                f[it.first] = f[nod];
                Q.push({D[it.first], it.first});
            }
            else if(len + it.second == D[it.first])
                f[it.first] = min(f[it.first], f[nod]);
    }
}

void init()
{
    for(int i = 1; i<=N; i++)
        D[i] = INT_MAX;
}

int main()
{
    ifstream fin("catun.in");
    ofstream fout("catun.out");
    fin >> N >> M >> K;
    init();
    for(int i = 1 ;i<=K; i++)
    {
        int numar;
        fin >> numar;
        is_catun[numar] = 1;
        D[numar] = 0;
        f[numar] = numar;
        Q.push({0,numar});
    }
    for(int i = 1; i<=M; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        E[x].pb({y, z});
        E[y].pb({x, z});
    }

    Dijkstra();

    for(int i = 1; i<=N; i++)
        if(is_catun[i])
            fout << "0 ";
        else
            fout << f[i] <<' ';
}