Cod sursa(job #2738638)

Utilizator Data 6 aprilie 2021 10:18:22 Algoritmul lui Dijkstra 100 cpp-64 done Arhiva educationala 1.67 kb
``````#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

typedef pair < int, int > Edge;

const int NMAX = 5e4 + 1;
const int INF = 1e9;

int N, M;

vector < Edge > G[NMAX];

int d[NMAX];
bool Sel[NMAX];

auto cmp = [] (Edge A, Edge B)
{
if(!(A.first < B.first))
return 1;

return 0;
};
priority_queue < Edge, vector < Edge >, decltype (cmp) > H(cmp);

{
f.tie(nullptr);

f >> N >> M;

for(int i = 1; i <= M; ++i)
{
int X = 0, Y = 0, C = 0;
f >> X >> Y >> C;

G[X].push_back({C, Y});
}

return;
}

static inline void Dijkstra (int S)
{
for(int i = 1; i <= N; ++i)
d[i] = INF, Sel[i] = 0;

d[S] = 0, Sel[S] = 1;

for(auto it : G[S])
if(it.first < d[it.second])
d[it.second] = it.first, H.push(it);

while(!H.empty())
{
while(!H.empty() && Sel[H.top().second])
H.pop();

if(H.empty())
return;

int Node = H.top().second;
int Cost = H.top().first;

Sel[Node] = 1;
H.pop();

for(auto it : G[Node])
if(Cost + it.first < d[it.second])
d[it.second] = Cost + it.first, H.push({Cost + it.first, it.second});
}

return;
}

static inline void Solve ()
{
Dijkstra(1);

for(int i = 2; i <= N; ++i)
{
g << ((d[i] != INF) ? d[i] : 0);

if(i != N)
g << ' ';
}

g << '\n';

return;
}

int main()
{