# Cod sursa(job #2760230)

Utilizator Data 24 iunie 2021 01:52:02 Algoritmul lui Dijkstra 100 cpp-64 done Arhiva educationala 2.08 kb
``````#include <bits/stdc++.h>
#define int long long int
#define double long double
#define cin fin
#define cout fout
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
void check()
{
cout<<"OK!\n";
}
class compar
{
public:
bool operator()(pair<int,int>a , pair<int,int>b)
{
return a.second> b.second;
}
};
class Dijkstra
{
priority_queue< pair<int,int>, vector< pair<int,int> >, compar>H;
int NMAX;
const int INF=999999999999999;
const int LAMBDA=10;
vector<int> uz;
vector<int> sol;
void prepare_start_node(const int& start_node)
{
sol[start_node]= 0;
H.push(make_pair(start_node, 0));
uz[start_node]=true;
}
public:
void ResizeSameN()
{
uz={0};
sol={INF};
}
Dijkstra(int n_no_lambda)
{
NMAX=n_no_lambda+LAMBDA;
uz.resize(NMAX,0);
sol.resize(NMAX,INF);

}
void djk( vector< vector< pair<int,int> > >& g,  int start_node,int  end_node)
{
bool flag_path=0;
prepare_start_node(start_node);
while(!H.empty())
{
pair<int,int> act= H.top(); H.pop();
uz[act.first]= false;

for(int i=0;i< g[act.first].size();i++)
{
int vec = g[act.first][i].first;
int cost = g[act.first][i].second;
if (sol[vec] > sol[act.first] + cost)
{

sol[vec] = sol[act.first] + cost;
if (!uz[vec])
{
uz[vec] = true;
H.push(make_pair(vec, sol[vec]));
}
}
}

}
//check();

}
int GetCost(int node)
{
if(sol[node]==INF)
return 0;
return sol[node];
}
};

int32_t main()
{
int n,m;
int i;
cin>>n>>m;
vector< vector< pair<int,int> > > g(n+1);
for(i=1;i<=m;i++)
{
int x,y,cost;
cin>>x>>y>>cost;
g[x].push_back(make_pair(y,cost));
}
Dijkstra d(n);
d.djk(g,1,n);
for(i=2;i<=n;i++)
cout<< d.GetCost(i)<<' ';
return 0;
}``````