Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2441999) | Cod sursa (job #2958125)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("dbz.in");
ofstream fout("dbz.out");
const int inf = 2e9;
struct NodeCost {
int node, cost;
bool operator<(const NodeCost other) const {
return this->cost > other.cost;
}
};
struct Edges {
int xx, yy, cc;
};
int N, M;
int d[1505], t[1505];
Edges e[30005];
priority_queue<NodeCost> pq;
vector<NodeCost> g[1505];
bool v[1505];
int Dijkstra(int s) {
for (int i = 1; i <= N; i++) {
d[i] = inf;
t[i] = 0;
v[i] = false;
}
d[s] = 0;
pq.push({s, 0});
while (!pq.empty()) {
int currentNode = pq.top().node;
pq.pop();
if (v[currentNode]) { continue; }
v[currentNode] = true;
for (auto muchie: g[currentNode]) {
int vecin = muchie.node, dist = muchie.cost;
if (d[currentNode] + dist < d[vecin]) {
d[vecin] = d[currentNode] + dist;
pq.push({vecin, d[vecin]});
if (currentNode == s) {
t[vecin] = vecin;
} else {
t[vecin] = t[currentNode];
}
}
}
}
t[s] = s;
int res = inf;
for (int i = 1; i <= M; i++) {
int x = e[i].xx;
int y = e[i].yy;
int c = e[i].cc;
if (t[x] != t[y] && ((x != s && y != s) || t[x] != x || t[y] != y)) {
res = min(res, d[x] + d[y] + c);
}
}
if (res != inf) { return res; }
return -1;
}
int main() {
fin >> N >> M;
for (int i = 1; i <= M; i++) {
int x, y, c;
fin >> x >> y >> c;
g[x].push_back({y, c});
g[y].push_back({y, c});
e[i] = {x, y, c};
}
for (int i = 1; i <= N; i++) {
fout << Dijkstra(i) << ' ';
}
return 0;
}