Pagini recente » Cod sursa (job #2726437) | Cod sursa (job #1714879) | Cod sursa (job #1336585) | Cod sursa (job #1607587) | Cod sursa (job #2303743)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
class heap
{
public :
int nod;
int price;
bool operator < (const heap & other_node ) const
{
return this->price > other_node.price;
}
};
struct edge
{
int node , cost;
};
vector < edge > v[50005];
priority_queue < heap > pq ;
int dist[50005];
bool was[50005];
const int oo = 1<<30;
int main()
{ int Nrnodes , Nredges ;
fin >> Nrnodes >> Nredges;
for(int i = 2 ; i <= Nrnodes ; i++)
dist[i] = oo ;
int edge1 , edge2 , cost;
for(int i = 1 ; i <= Nredges ; i ++)
{
fin >> edge1 >> edge2 >> cost ;
v[edge1].push_back(edge{edge2,cost});
}
pq.push(heap{1,0});
while(pq.empty()==0)
{
int costmin = pq.top().price;
int nodul = pq.top().nod;
was[nodul]=1;
pq.pop();
for(int i = 0 ; i < (v[nodul].size() ; i++)
if(was[v[nodul][i].node]==0)
if(costmin + v[nodul][i].cost < dist[v[nodul][i].node])
{
dist[v[nodul][i].node] = costmin + v[nodul][i].cost ;
pq.push(heap{v[nodul][i].node,dist[v[nodul][i].node]});
}
}
for(int i = 2 ; i <= Nrnodes ; i++)
if(dist[i] == oo)
fout << 0 << " ";
else
fout << dist[i] << " " ;
return 0;
}