Pagini recente » Cod sursa (job #290929) | Cod sursa (job #1132132) | Cod sursa (job #42066) | Cod sursa (job #3257132) | Cod sursa (job #1323683)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <sstream>
#include <deque>
#include <bitset>
#include <complex>
#include <functional>
#include <memory>
#include <numeric>
using namespace std;
#define x first
#define y second
int main () {
vector<pair<int, int>> G[50001];
vector<int> C(50001, 1<<30);
int n, m;
FILE *in, *out;
in = fopen("dijkstra.in", "rt");
out = fopen("dijkstra.out", "wt");
fscanf(in, "%d %d", &n, &m);
for(int i = 0; i < m; i++) {
int s, e, c;
fscanf(in, "%d %d %d", &s, &e, &c);
G[s].push_back({e, c});
}
priority_queue<pair<int, int>> q;
q.push({0, 1});
C[1] = 0;
while(!q.empty()) {
auto c = q.top();
q.pop();
for(int i = 0; i < G[c.y].size(); i++){
if(C[G[c.y][i].x] > C[c.y] + G[c.y][i].y) {
C[G[c.y][i].x] = C[c.y] + G[c.y][i].y;
q.push({C[G[c.y][i].x], G[c.y][i].x});
}
}
}
for(int i = 2; i <= n; i++) {
fprintf(out, "%d ", C[i]);
}
return 0;
}