1725M - Moving Both Hands - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define endl  "\n"
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define sz(x) (int)((x).size())
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define rep(i, a) for (int i = 0; i < a; i++)
#define ii pair<int, int>
#define debug(x) cout << #x << "  " << x << "\n"
#define vi vector<int>
#define vii vector<pair<int, int>>
#define mem(c, a) memset(c, a, sizeof(c))
#define setbit(x) __builtin_popcountll(x)
const int INF = 1e18;
const int N = 1e5 + 7;
const double eps = 1e-6;
const int mod = 998244353;
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());

vector<vector<pair<int, int>>> adj(N), rev(N); int n;

void d1(int s, vector<int> & d) {

   d[s] = 0;
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
              //  p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

void d2(vi &d)
{
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
	fr(i,1,n)
	{
		if(d[i] < INF) 
		q.push({d[i],i});
	}
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : rev[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
             //   p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

void solve(int t_case)
{ 
   cin>>n; int m; cin>>m;
   vi d(n+1,INF);
   d[1] = 0;
   rep(i,m)
   {
	 int x,y,w; cin>>x>>y>>w;
	 adj[x].push_back({y,w});
     rev[y].push_back({x,w});
   }
   d1(1,d);
   d2(d);
   fr(i,2,n)
   {
	if(d[i] < INF)
	{
		cout<<d[i]<<' ';
	}
	else cout<<"-1 ";
   }

}

signed main()
{
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
// cout << setprecision(12) << fixed;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	//sieve();
	int tests = 1;
	//cin>>tests;

	fr(i, 1, tests) solve(i);
	return 0;
}