Cod sursa(job #733335)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 50010;
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;
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf ("%d%d",&n,&m);
for (int i = 1;i <= m;++i)
{
scanf("%d%d%d",&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)
printf ("%d ",d[i]);
}
int main()
{
citire();
dijkstra(1);
afisare();
return 0;
}