Pagini recente » Borderou de evaluare (job #628657) | Borderou de evaluare (job #735286) | Cod sursa (job #572252) | Cod sursa (job #1169367)
#include <fstream>
#include <set>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int inf = 0x3f3f3f3f;
int N, M;
int cost[50010];
set<pair<int, int> > G[50010];
queue<int> Q;
inline int max(const int &val, const int &_val) { return (val < _val) ? (_val) : (val); }
inline int min(const int &val, const int &_val) { return (val > _val) ? (_val) : (val); }
int main()
{
int i, A, B, C, node;
set<pair<int, int> >::iterator it;
cin >> N >> M;
fill_n(cost + 2, N, inf);
for (i = 0; i < M; ++i)
{
cin >> A >> B >> C;
G[A].insert(make_pair(B, C));
}
Q.push(1);
while(!Q.empty())
{
node = Q.front();
for (it = G[node].begin(); it != G[node].end(); ++it)
{
if (cost[node] + it->second < cost[it->first])
{
cost[it->first] = cost[node] + it->second;
Q.push(it->first);
}
}
Q.pop();
}
for (i = 2; i <= N; ++i)
{
if (cost[i] == inf)
cout << "0 ";
else cout << cost[i] << ' ';
}
cout << '\n';
cout.close();
return 0;
}