Cod sursa(job #814707)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define maxV 10000
#define INF 100000000
bool operator<(const pair<int,int> &leftNode, const pair<int,int>&rightNode) {
if (leftNode.first != rightNode.first) return leftNode.first < rightNode.first;
if (leftNode.second != rightNode.second) return leftNode.second < rightNode.second;
return false;
};
int V;
vector< pair<int,int> > g[maxV];
int dist[maxV];
int prev[maxV];
int proc[maxV];
void shortestPath(int s) {
priority_queue< pair<int,int> > Q;
for(int i = 0; i < V; i++)
dist[i] = INF;
dist[s] = 0;
for(int i = 0; i < V; i++)
Q.push(make_pair(dist[i], i));
while(!Q.empty())
{
int v = Q.top().second;
Q.pop();
for(int i = 0; i < g[v].size(); i++)
{
int w = g[v][i].second;
int x = g[v][i].first;
if(dist[x] > dist[v] + w){
dist[x] = dist[v] + w;
prev[x] = v;
Q.push(make_pair(dist[x], x));
}
}
}
}
int main()
{
int m;
int tea, teb, tec;
cin>>V>>m;
for(int i=0;i<m;i++)
{
cin>>tea>>teb>>tec;
g[tea].push_back(make_pair(teb, tec));
g[teb].push_back(make_pair(tea, tec));
}
V++;
shortestPath(1);
for(int i=2;i<V;i++)
cout<<dist[i]<<' ';
cout<<"\n";
}
// }
// prev.assign(n, -1);
// int mini=0;
// // "e < f" <=> "e.weight > f.weight"
// for (prev[dest] == -1) {
// for(int i=1;i<V;i++)
// if((dist[i]<dist[mini])&&(prev[i] == -1))
// mini=i;
// for(int i=0;i<g[mini].size();i++)
// {
// if(dist[g[mini].])
// }
// Edge e = Q.front(); Q.pop();
// if (prev[e.dst] != -1)
// continue;
// prev[e.dst] = e.src;
// for(int i = 0; i < g[e.dst].size(); i++)
// {
// int v = g[e.dst][i].first;
// int w = g[e.dst][i].second;
// if(dist[v] > e.weight + w)
// {
// dist[v] = e.weight + w;
// Q.push(Edge(e.dst, v, w + e.weight))
// }
// }
// FOR(f,g[e.dst]) {
// if (dist[f->dst] > e.weight+f->weight) {
// dist[f->dst] = e.weight+f->weight;
// Q.push(Edge(f->src, f->dst, e.weight+f->weight));
// }
// }
// }
/*vector<int> buildPath(const vector<int> &prev, int t) {
vector<int> path;
for (int u = t; u >= 0; u = prev[u])
path.push_back(u);
reverse(path.begin(), path.end());
return path;
}*/