Submission #23979431

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define endl '\n'
#define TIME 1.0*clock()/CLOCKS_PER_SEC
#define pii pair < int , int >
#define Endl '\n'

#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

template <typename T>
    using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;
const int FFTM = 998244353;

const int SX[4] = {0 , 1 , -1 , 0};
const int SY[4] = {1 , 0 , 0 , -1};
const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};

typedef cc_hash_table< int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>, hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>> ht;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("console.in", "r", stdin);
//    freopen("console.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector < vector < pair < int, int > > > G(n);
    for (int i = 0;i < m; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        G[x].pb({y, z});
    }
    ll ans = 0;
    for (int i = 0;i < n; ++i){

            vector < int > dist(n, 1e9);
            vector < int > ot(n, 1e9);
            priority_queue < pair < int, int > > q;
            q.push({0, i});
            dist[i] = 0;
            ot[i] = 0;
            int j = 0;
            do{
                while(!q.empty()){
                    int v = q.top().S;
                    int d = -q.top().F;
                    q.pop();
                    if (dist[v] != d)continue;
                    for (auto to : G[v]){
                        if (to.F > j){
                            if (ot[to.F] > dist[v] + to.S){
                                ot[to.F] = dist[v] + to.S;
                            }
                            continue;
                        }
                        if (dist[to.F] > dist[v] + to.S){
                            dist[to.F] = dist[v] + to.S;
                            ot[to.F] = dist[to.F];
                            q.push({-dist[to.F], to.F});
                        }
                    }
                }
                for (auto to : ot)if (to != 1e9)ans += to;
                j++;
                if (j == n)break;
                dist[j] = ot[j];
                if (dist[j] != 1e9)q.push({-dist[j], j});
            }while(1);

    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result