Pagini recente » Rezultatele filtrării | Cod sursa (job #2081811) | Cod sursa (job #2588026) | Cod sursa (job #2850474) | Cod sursa (job #2917988)
#include <cstdio>
#include <cstdio>
#include <queue>
#include <tuple>
#define INF 0x3f3f3f3f
std::vector<std::vector<std::pair<int,int>>> G; // G[i] -> (c, j) = (i -c-> j)
std::vector<int> DP;
std::priority_queue<std::pair<int, int>> PQ;
int N, M;
void dijkstra(int k)
{
DP.resize(N);
fill(DP.begin(), DP.end(), INF);
DP[k] = 0;
PQ.emplace(-0, k);
int cost;
while (!PQ.empty()) {
std::tie(cost, k) = PQ.top();
cost *= -1;
PQ.pop();
if (DP[k] != cost) continue;
for (auto it: G[k])
if (DP[it.second] > DP[k] + it.first) {
DP[it.second] = DP[k] + it.first;
PQ.emplace(-DP[it.second], it.second);
}
}
for (int i = 1; i < N; ++i)
if (DP[i] >= INF)
printf("0 ");
else
printf("%d ", DP[i]);
}
int main()
{
freopen("dijkstra.in", "r", stdin);
freopen("dijkstra.out", "w", stdout);
scanf("%d%d", &N, &M);
G.resize(N);
int a, b, c;
for (int i = 0; i < M; ++i) {
scanf("%d%d%d", &a, &b, &c);
--a; --b;
G[a].emplace_back(c, b);
}
dijkstra(0);
return 0;
}