Mai intai trebuie sa te autentifici.
Cod sursa(job #3227785)
Utilizator | Data | 2 mai 2024 16:40:27 | |
---|---|---|---|
Problema | Algoritmul lui Dijkstra | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.05 kb |
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
long long INF = 1e18;
priority_queue<pair<int, int> , vector<pair<int, int>> , greater<pair<int, int>> > Q;
vector<pair<int,int>>mat[50001];
int n, m;
long long dist[50001];
void djiksra(int start){
for(int i = 1; i<=n; i++)dist[i] = INF;
Q.push({0, start});
while(!Q.empty()){
int distance = Q.top().first;
int nod = Q.top().second;
Q.pop();
if(distance > dist[nod])
continue;
for(auto vecin: mat[nod]){
if(distance + vecin.second < dist[vecin.first] ){
dist[vecin.first] = distance + vecin.second;
Q.push({dist[vecin.first], vecin.first});
}
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i<=m; i++){
int x, y, c;
cin >> x >> y >> c;
mat[x].push_back({y, c});
}
djiksra(1);
for(int i = 2; i<=n; i++){
cout << dist[i] << ' ';
}
return 0;
}