Cod sursa(job #2650962)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 21 septembrie 2020 08:23:42
Problema Drumuri minime Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <cfloat>
using namespace std;

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

vector <pair <int, long double>> v[1501];
pair <long double, int> d[1501];

struct el
{
    long double c;
    int nod;
    bool operator <(const el &alt) const
    {
        if (abs(c - alt.c) <= 10*LDBL_EPSILON) //consideram costurile egale
            return 0;
        return c > alt.c;
    }
};

priority_queue <el> p;
bool b[1501];

int main()
{
    int n, m, i, j, x, y, z;
    long double c;
    fin >> n >> m;
    for (i = 1; i<=m; i++)
    {
        fin >> x >> y >> z;
        c = log2(z);
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    
    for (i = 1; i<=n; i++)
        d[i] = {100000, 0};
    d[1] = {0, 1};
    p.push({0, 1});
    
    for (i = 1; i<=n; i++)
    {
        while (p.empty() == 0 && b[p.top().nod])
            p.pop();
        if (p.empty() == 1)
            break;
    
        x = p.top().nod;
        p.pop();
        b[x] = 1;
        
        for (j = 0; j<v[x].size(); j++)
        {
            if (abs(d[v[x][j].first].first - (d[x].first + v[x][j].second)) <= 10*LDBL_EPSILON)
            {
                d[v[x][j].first].second = (d[v[x][j].first].second + d[x].second)%104659;
                p.push({d[v[x][j].first].first, v[x][j].first});
            }
            else if (d[v[x][j].first].first > d[x].first + v[x][j].second)
            {
                d[v[x][j].first].first = d[x].first + v[x][j].second;
                d[v[x][j].first].second = d[x].second;
                p.push({d[v[x][j].first].first, v[x][j].first});
            }
        }
    }
    for (i = 2; i<=n; i++)
        fout << d[i].second << ' ';
    return 0;
}