Pagini recente » Borderou de evaluare (job #338185) | Cod sursa (job #733339)
Cod sursa(job #733339)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 50010;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct mch
{
int dest,dist;//destinatie si distanta
};
priority_queue< pair<int,int>,vector< pair<int,int> >, greater< pair<int,int> > > heap;
vector<mch> vecin[MAXN];
int d[MAXN];
int n,m;
void citire()
{
int a,b,c;
in >> n >> m;
for (int i = 1;i <= m;++i)
{
in >> a >> b >> c;
vecin[a].push_back((mch){b,c});
}
}
void initializare_d()
{
for (int i = 1;i <= n;++i)
d[i] = -1;
}
void dijkstra(int s)
{
int nod;
//golire_heap
initializare_d();
heap.push(make_pair(0,s));
while (!heap.empty())
{
while (!heap.empty() && d[heap.top().second] != -1)
heap.pop();
if (heap.empty())
break;
nod = heap.top().second;
d[nod] = heap.top().first;
for (unsigned int i = 0;i < vecin[nod].size();++i)
heap.push(make_pair(d[nod] + vecin[nod][i].dist,vecin[nod][i].dest));
}
}
void afisare()
{
for (int i = 2;i <= n;++i)
out << ((d[i] != -1)?d[i]:0) << " ";
}
int main()
{
citire();
dijkstra(1);
afisare();
return 0;
}