Codeforces 1725M / Dijkstra Variant

/***
 created: 2022-09-05-02.38.26
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

vector<pair<ll,ll>>g[100005],gr[100005];

ll cost[100005];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n,m,i,j,k,l;

    cin>>n>>m;

    for(i=0;i<m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        gr[v].push_back({u,w});
    }

    //solution -> -> -> <- <- <- (max 1 reverse)

    fill(cost,cost+100002,1e17);

    priority_queue <pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;

    q.push({0,1});

    cost[1]=0;

    while(!q.empty())
    {
        auto d=q.top();
        q.pop();

        if(cost[d.second]<d.first) continue;

        for(auto u:g[d.second])
        {
            if(cost[u.first]> u.second+d.first)
            {
                cost[u.first]=u.second+d.first;
                q.push({cost[u.first],u.first});
            }
        }
    }

    for(i=1;i<=n;i++)
    {
        q.push({cost[i],i});
    }

    //reverse move

    while(!q.empty())
    {
        auto d=q.top();
        q.pop();

        if(cost[d.second]<d.first) continue;

        for(auto u:gr[d.second])
        {
            if(cost[u.first]> u.second+d.first)
            {
                cost[u.first]=u.second+d.first;
                q.push({cost[u.first],u.first});
            }
        }
    }

    for(i=2;i<=n;i++)
    {
        if(cost[i]==1e17) cout<<-1<<" ";
        else cout<<cost[i]<<" ";
    }

    cout<<nl;

    get_lost_idiot;
}