Cod sursa(job #2718684)

Utilizator Codrut112Codrut Copas Codrut112 Data 8 martie 2021 23:26:02
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,a[250001][4],rasp[50001],x,y,z,i,ok,nr;
int main()
{
    f>>n;
    f>>m;
    nr=1;

    ok=0;
    for(i=2; i<=n; i++)rasp[i]=200000000;
    rasp[1]=0;
    for(i=1; i<=m; i++)
    {
        f>>a[i][1]>>a[i][2]>>a[i][3];
        if(a[i][1]==1)rasp[a[i][2]]=a[i][3];
    }
    while(ok==0 and nr<n-1)
    {
        ok=1;
        for(i=1; i<=m; i++)
        {
            x=a[i][1];
            y=a[i][2];
            z=a[i][3];
            if(rasp[x]+z<rasp[y])
            {
                rasp[y]=rasp[x]+z;
                ok=0;
            }
        }
        nr++;
    }
    for(i=2; i<=n; i++)if(rasp[i]!=200000000)g<<rasp[i]<<" ";
        else g<<0<<" ";
}