Submission #1291127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291127		behesht	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	308 ms	22288 KiB

commuter_pass

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e18 + (35 / 10); // 35 ---> 36
const int MAXN = 2e5 + (35 / 10); // 35 ---> 36

int dis[MAXN][4], a[4], n, m;
int mini[MAXN][2], ans = INF;
vector <arr(2)> adj[MAXN];

void dij(int x){

    set <arr(2)> s;

    for(int i = 0; i < n; i++)
        dis[i][x] = INF;

    dis[a[x]][x] = 0;
    s.insert({0, a[x]});

    while(!s.empty()){
        auto [_, u] = *s.begin();
        s.erase(s.begin());

        for(auto [v, w] : adj[u]){
            if(dis[v][x] > dis[u][x] + w){
                dis[v][x] = dis[u][x] + w;
                s.insert({dis[v][x], v});
            }
        }
    }

    // d1(U + 1);
    // for(int i = 0; i < n; i++)
    //     d2(i + 1, dis[i][x]);
    // cout << endl;
}

void solve(int U, int x){

    set <arr(2)> s;
    s.insert({0, U});

    while(!s.empty()){
        auto [_, u] = *s.begin();
        s.erase(s.begin());
        
        for(auto [v, w] : adj[u]){

            if(dis[v][0] + dis[v][1] == dis[u][0] + dis[u][1]){

                if(w + dis[v][x ^ 1] == dis[u][x ^ 1]){
                    mini[v][0] = min(mini[v][0], mini[u][0]);
                    mini[v][1] = min(mini[v][1], mini[u][1]);
    
                    s.insert({dis[v][x], v});
                }
            }
        }

        // ans = min(ans, mini[u][0] + mini[u][1]);
    }
}

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

    cin >> n >> m;

    for(int i = 0; i < 4; i++){
        cin >> a[i];
        a[i]--;
    }

    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;

        u--;
        v--;

        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    for(int i = 0; i < 4; i++)
        dij(i);

    for(int i = 0; i < n; i++){
        mini[i][0] = dis[i][2];
        mini[i][1] = dis[i][3];

        // d1(i);
        // d4(dis[i][0], dis[i][1], dis[i][2], dis[i][3]);
    }
    
    solve(a[0], 0);
    solve(a[1], 1);

    for(int i = 0; i < n; i++){
        ans = min(ans, mini[i][0] + mini[i][1]);
        // d3(i + 1, mini[i][0], mini[i][1]);
    }

    if(ans >= 1000000000000000)
        ans = -1;
    
    cout << ans << endl;
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 

*/

/*
8 8

1 8
1 8

1 2 100000
2 3 8458984
3 4 846988
4 5 848488
5 6 44
6 7 55555
7 5 5963
1 9 10
*/

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45