Untitled
/// Msaa el 5ra #pragma GCC optimize("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target("avx,avx2,fma") #include "bits/stdc++.h" using namespace std; #define pb push_back #define F first #define S second #define f(i, a, b) for(int i = a; i < b; i++) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define sz(x) (int)(x).size() #define mp(x, y) make_pair(x,y) #define popCnt(x) (__builtin_popcountll(x)) #define int ll using ll = long long; using ii = pair<int, int>; using ull = unsigned long long; const int N = 1e6 + 5, LG = 18, MOD = 1e9 + 7; const long double PI = acos(-1); const long double EPS = 1e-7; const int NODES = 305; int n, m; vector<array<int, 3>> adj[NODES]; void doWork() { cin >> n >> m; vector<int> ans(m, -1); f(i, 0, m) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w, i}); adj[v].pb({u, w, i}); } f(i, 1, n + 1) { vector<ii> a(n + 1, ii(1e10, -1)); ///record smallest distance and what you used vector<ii> b(n + 1, ii(1e10, -1)); ///record second smallest distance and what you used using iii = tuple<int, int, int>; priority_queue<iii, vector<iii>, greater<iii>> pq; a[i] = ii(0, 0); b[i] = ii(0, 0); for (auto [to, wt, e]: adj[i]) { a[to] = ii(wt, to); pq.push({wt, to, to}); } while (pq.size()) { auto [dist, node, cur] = pq.top(); pq.pop(); if (ii(dist, cur) != a[node] && ii(dist, cur) != b[node]) continue; for (auto [to, wt, e]: adj[node]) { if (i == to)continue; int d = wt + dist; if (d < a[to].F) { if (a[to].S != cur) b[to] = a[to]; a[to] = ii(d, cur); pq.push({d, to, cur}); } else if (cur != a[to].S && d < b[to].F) { b[to] = ii(d, cur); pq.push({d, to, cur}); } } } for (auto [to, wt, e]: adj[i]) { if (a[to].S != to) ans[e] = a[to].F; else if (b[to].S != to && b[to].S != -1)ans[e] = b[to].F; } } f(i, 0, m) cout << ans[i] << '\n'; } int32_t main() { #ifdef ONLINE_JUDGE ios_base::sync_with_stdio(0); cin.tie(0); #endif // ONLINE_JUDGE int t = 1; // cin >> t; while (t--) { doWork(); } }
Leave a Comment