Pagini recente » Borderou de evaluare (job #1048043) | Borderou de evaluare (job #1940018) | Borderou de evaluare (job #1740699) | Borderou de evaluare (job #1611872) | Cod sursa (job #2128810)
#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e4, maxM = 25e4, INF = 0x3f3f3f3f;
vector < pair <int, int> > G[maxN];
priority_queue < pair <int, int> > heap;
int dist[maxN + 5];
void dijkstra(int start){
heap.push({0, start});
int node, d, son, cost;
while (!heap.empty()){
node = heap.top().second;
d = -heap.top().first;
heap.pop();
if (d > dist[node])
continue;
for (pair<int, int> edge : G[node]){
son = edge.first;
cost = edge.second;
if (d + cost < dist[son]){
dist[son] = d + cost;
heap.push({-dist[son], son});
}
}
}
}
int main(){
freopen("dijkstra.in", "r", stdin);
freopen("dijkstra.out", "w", stdout);
int N, M, A, B, C;
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; i++){
scanf("%d %d %d", &A, &B, &C);
G[A].push_back({B, C});
}
memset(dist, INF, sizeof(dist));
dist[1] = 0;
dijkstra(1);
for (int i = 2; i <= N; i++)
if (dist[i] == INF)
printf("0 ");
else
printf("%d ", dist[i]);
return 0;
}