Cod sursa(job #2980430)

Utilizator lilpmarioPuiu Mario lilpmario Data 16 februarie 2023 15:05:33
Problema Algoritmul lui Dijkstra Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int nrmx=1e5+5, inf=1e9;
vector<pair<int,int>> G[nrmx];
priority_queue<pair<int , int > >q;
bool v[nrmx];
int n,m,p;
int D[nrmx];

void read()
{
    int x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    f>>x>>y>>c, G[x].push_back({y,c}),G[y].push_back({x,c});
}
void dijkstra(int x)
{
    q.push({0,x});
    while(!q.empty())
    {
        x=q.top().second;
        q.pop();
        if(!v[x])
        {
            for(int i=0; i<G[x].size(); i++)
            if(D[x]+G[x][i].second<D[G[x][i].first])
            {
                D[G[x][i].first]=D[x]+G[x][i].second;
                q.push({-D[G[x][i].first],G[x][i].first});
            }
            v[x]=1;
        }
    }
}
int main()
{
    read();
    for(int i=1;i<=n;i++)
        D[i]=inf;
        D[1]=0;
    dijkstra(1);

    for(int i=2;i<=n;i++)
        if(D[i]==inf) g<<0<<" ";
        else g<<D[i]<<" ";
}