Cod sursa(job #2967678)

Utilizator stefan05Vasilache Stefan stefan05 Data 19 ianuarie 2023 22:51:22
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <set>

#define NMAX 50005
#define INF 10000005

using namespace std;

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

struct Arc
{
    int vf, c;
};

int n, m, x0;
int x, y, c;
vector<Arc> cost[NMAX];
int dmin[NMAX];
int minim, vfmin;
int vfcrt, costcrt;
int i, j;

//int pre[NMAX];

set<pair<int, int>> s;

void afisare(int);

int main()
{
    ///CITIRE
    fin >>n>>m; x0 = 1;
    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y>>c;
        cost[x].push_back({y, c});
    }

    ///ALG. LUI DIJKSTRA
    for (i = 1; i <= n; ++i)
    {
        dmin[i] = INF;
        //pre[i] = x0;
    }
    dmin[x0] = 0;
    //pre[x0] = 0

    s.insert(make_pair(x0, 0));
    while (!s.empty())
    {
        vfmin = (*s.begin()).first; minim = (*s.begin()).second;
        s.erase(s.begin());
        for (i = 0; i < cost[vfmin].size(); ++i)
        {
            vfcrt = cost[vfmin][i].vf;
            costcrt = cost[vfmin][i].c;
            if (dmin[vfcrt] > minim + costcrt)
            {
                if (dmin[vfcrt] != INF)
                    if (s.find(make_pair(vfcrt, dmin[vfcrt])) != s.end())
                        s.erase(s.find(make_pair(vfcrt, dmin[vfcrt])));
                dmin[vfcrt] = minim + costcrt;
                //pre[vfcrt] = vfmin;
                s.insert(make_pair(vfcrt, dmin[vfcrt]));
            }
        }
    }

    ///AFISARE
    for (i = 2; i <= n; ++i)
        if (dmin[i] == INF) fout <<0<<' ';
        else fout <<dmin[i]<<' ';
    fout <<'\n';

    //afisare(1);
    fout.close();
    return 0;
}

/*void afisare(int vf)
{
    if (vf == x0)
    {
        fout <<x0<<' ';
        return;
    }

    afisare(pre[vf]);
    fout <<vf<<' ';
}*/