Cod sursa(job #2309209)

Utilizator Data 28 decembrie 2018 16:41:15 Drumuri minime 80 cpp-64 done Arhiva de probleme 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <vector>
#include <set>
#define MAX 1500000000005
#define mod 104659
#define ull unsigned long long
using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

ull n, m, from, to, cost, energii[1505], nr[1505];

bool onq[1505];

vector<pair<ull, ull > >graph[1505];

bool operator<(pair<ull,ull>p1, pair<ull,ull>p2)
{
if (p1.second==p2.second)
return p1.first<p2.first;
return p1.second<p2.second;
}

set<pair<int,int> >q;

void citire()
{
f >> n >> m;
for (int i=1; i<=m; i++)
{
f >> from >> to >> cost;
graph[from].push_back(make_pair(to,cost));
graph[to].push_back(make_pair(from,cost));

}
}

void dijkstra()
{
for (int i=2; i<=n; i++)
{
energii[i]=MAX;
}
nr[1]=1;
q.insert({1,0});
onq[1]=true;
while (!q.empty())
{
ull nod=q.begin()->first;
onq[nod]=false;
q.erase(q.begin());
for (auto &v:graph[nod])
{
ull vecin=v.first;
ull cost=v.second;
if (energii[nod]+cost<energii[vecin])
{
energii[vecin]=energii[nod]+cost;
nr[vecin]=nr[nod];
if (!onq[vecin]) {
q.insert({vecin, energii[vecin]});
onq[vecin]=true;
}
}
else if (energii[nod]+cost==energii[vecin])
{
nr[vecin]+=nr[nod];
nr[vecin]%=mod;

}
}
}
for (int i=2; i<=n; i++)
g << nr[i] <<' ';
}

int main() {
citire();
dijkstra();
return 0;
}