General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
184436818 Practice:
satanshoo
1725M - 3 C++14 (GCC 6-32) Accepted 373 ms 21588 KB 2022-12-09 11:56:10 2022-12-09 11:56:10
→ Source
#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 2e5+5;
const int mod = 998244353;
const int inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()


int inv(int i) {if (i == 1) return 1; return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;}
 
int mod_mul(int a, int b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}
 
int mod_add(int a, int b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}
 
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
 
int ceil_div(int a, int b) {return a % b == 0 ? a / b : a / b + 1;}
 
int pwr(int a, int b) {a %= mod; int res = 1; while (b > 0) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}

//////////////////////////// TEMPLATE ////////////////////////////////////

void solve()
{              
        int n, m;
        cin >> n >> m;

        vector<pair<int,int>>g[n+1], rev_g[n+1];
        for(int i = 0 ; i < m; ++i){
                int x, y, wt;
                cin >> x >> y >> wt;
                g[x].push_back({y,wt});
                rev_g[y].push_back({x,wt});
        }

                   // wt, node 
        multiset<pair<int,int>>s;
        vector<int>vis(n+1, 0);
        vector<int>dis(n+1, inf);

        //dijsktra 1 starts
        s.insert({0,1});
        dis[1] = 0;
        
        while(!s.empty()){
                auto f = *s.begin();
                int v_dis = f.first;
                int v = f.second;
                s.erase(*s.begin());
                if(vis[v])continue;
                vis[v] = 1;
                for(auto child : g[v]){
                        int child_v = child.first;
                        int wt = child.second;
                        if(wt + dis[v] < dis[child_v]){
                                dis[child_v] = wt + dis[v];
                                s.insert({dis[child_v],child_v});
                        }
                }
        }
        

        for(int i = 0; i <= n; ++i){
                vis[i] = 0;
        }
        for(int i = 1; i <= n; ++i){
                s.insert({dis[i],i});
        }
        while(!s.empty()){
                auto f = *s.begin();
                int v_dis = f.first;
                int v = f.second;
                s.erase(*s.begin());
                if(vis[v])continue;
                vis[v] = 1;
                for(auto child : rev_g[v]){
                        int child_v = child.first;
                        int wt = child.second; 
                        if(wt + dis[v] < dis[child_v]){
                                dis[child_v] = wt + dis[v];
                                s.insert({dis[child_v],child_v});
                        }
                }
        }
        for(int i = 2; i <= n; ++i){
                if(dis[i] == inf){
                        cout << -1 << " ";
                }
                else{
                        cout << dis[i] << " ";
                }
        }
} 

signed main(){
#ifndef ONLINE_JUDGE
        freopen("inputF.in", "r", stdin);
        freopen("outputF.in", "w", stdout);
#endif
        fast_io;
       
        int t = 1;
        // cin>>t;
        while(t--){
                solve();
                
        } 

        return 0;
}
        
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details