Cod sursa(job #2706232)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 14 februarie 2021 12:58:31
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.2 kb
#include <bits/stdc++.h>
#define NMAX 36005
#define BIGNUM 99999999999
using namespace std;

/*********************************************/
/// INPUT / OUTPUT

ifstream f("catun.in");
ofstream g("catun.out");
/*********************************************/
/// GLOBAL DECLARATIONS

int N, M, K, nr, ans[NMAX];
bool fortress[NMAX];
long long sol[NMAX];

struct Node
{
    int node, dist, ft;
} heap[2 * NMAX];

vector < Node > adjacency[NMAX];
vector < int > fortresses;
map < int, bool > visited[NMAX];
/*********************************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*********************************************/
///-----------------------------------------------------
inline void ReadInput()
{
    f >> N >> M >> K;

    for(int i = 1 ; i <= K ; ++ i)
    {
        int fortressIdx;
        f >> fortressIdx;
        fortress[fortressIdx] = true;
        fortresses.push_back(fortressIdx);
    }

    for(int i = 1 ; i <= M ; ++ i)
    {
        int a, b, c;

        f >> a >> b >> c;

        adjacency[a].push_back({b, c});
        adjacency[b].push_back({a, c});
    }
}
///-----------------------------------------------------
void AddToHeap(int node, int dist, int ft)
{
    nr ++;
    heap[nr].node = node;
    heap[nr].dist = dist;
    heap[nr].ft = ft;

    int pos = nr;

    while(pos / 2 > 0 && heap[pos / 2].dist > heap[pos].dist)
    {
        swap(heap[pos], heap[pos / 2]);
        pos /= 2;
    }
}
///-----------------------------------------------------
void RemoveFromHeap()
{
    swap(heap[1], heap[nr]);
    nr--;

    int pos = 1;

    while(2 * pos + 1 <= nr && (heap[pos].dist > heap[2 * pos].dist || heap[pos].dist > heap[2 * pos + 1].dist))
    {
        if(heap[2 * pos].dist < heap[2 * pos + 1].dist)
        {
            swap(heap[2 * pos], heap[pos]);
            pos *= 2;
        }
        else
        {
            swap(heap[pos], heap[2 * pos + 1]);
            pos = pos * 2 + 1;
        }
    }

    if(pos == nr / 2 && heap[pos].dist > heap[nr].dist)
        swap(heap[pos], heap[nr]);
}
///-----------------------------------------------------
inline void Solution()
{
    for(int i = 1 ; i <= N ; ++ i)
        sol[i] = BIGNUM;

    for(int i = 0 ; i < K ; ++ i)
        AddToHeap(fortresses[i], 0, fortresses[i]);

    while(nr > 0)
    {
        int node = heap[1].node;
        int dist = heap[1].dist;
        int ft = heap[1].ft;

        RemoveFromHeap();

        if(sol[node] == BIGNUM)
        {
            sol[node] = dist;
            ans[node] = ft;

            for(auto it: adjacency[node])
            {
                if(sol[it.node] == BIGNUM)
                    AddToHeap(it.node, it.dist + dist, ft);
            }
        }
    }
}
///-----------------------------------------------------
inline void Output()
{
    for(int i = 1 ; i <= N ; ++ i)
    {
        if(fortress[i] || sol[i] == BIGNUM)
            g << "0 ";
        else
            g << ans[i] << " ";
    }

}
///-----------------------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}