Submission #1273180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273180		hiepsimauhong	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	416 ms	56912 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ll = long long;

#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A,L,R) FOR(OK, L, R){if(A[OK]<=-oo / 10||A[OK]>=oo)cout<<"- ";else cout<<A[OK]<<' ';}cout<<'\n';
#define prints(A) FOA(OK, A){cout<<OK<<' ';}cout << '\n';
#define printz(A,L,R) FOR(OK, 0, L){FOR(KO, 1, R){if(A[OK][KO]>-oo&&A[OK][KO]<oo)cout<<A[OK][KO]<<' ';else cout << "- ";} cout << '\n';}cout << '\n';

#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;

int n, m, s, t, st, en;
vector<int> g[N];
ii edge[N];
int cost[N];

struct Dijkstra{
        int start;
        int dist[N];
        bool vis[N];

        vector<int> tr[N], ing[N], rev[N];
        priority_queue<ii, vector<ii>, greater<ii>> pq;

        void shortest(){
                FOR(i, 1, n){
                        dist[i] = oo;
                }
                dist[start] = 0;
                pq.push({0, start});

                while(!pq.empty()){
                        int u = pq.top().sd;
                        int c = pq.top().fs;
                        pq.pop();

                        if(c > dist[u]){
                                continue;
                        }

                        FOA(i, g[u]){
                                int v = (edge[i].fs ^ edge[i].sd ^ u);
                                int w = cost[i];

                                if(dist[v] > dist[u] + w){
                                        dist[v] = dist[u] + w;
                                        pq.push({dist[v], v});
                                        tr[v].clear();
                                        tr[v].push_back(i);
                                }
                                else if(dist[v] == dist[u] + w){
                                        tr[v].push_back(i);
                                }
                        }
                }
        }

        void build(int u){
                vis[u] = 1;
                FOA(i, tr[u]){
                        int v = (edge[i].fs ^ edge[i].sd ^ u);
                        ing[v].push_back(u);
                        rev[u].push_back(v);

                        if(!vis[v]){
                                build(v);
                        }
                }
        }
} d1;

namespace Road{
        static int dist[4][N];
        static priority_queue<iii, vector<iii>, greater<iii>> pq;

        void add(int val, int keep, int u){
                pq.push({val, {keep, u}});
        }

        int Dijkstra(){
                memset(dist, 0x3f, sizeof dist);
                dist[0][st] = 0;

                pq.push({0, {0, st}});

                while(!pq.empty()){
                        int u = pq.top().sd.sd;
                        int c = pq.top().fs;
                        int k = pq.top().sd.fs;
                        pq.pop();

                        if(c > dist[k][u]){
                                continue;
                        }

                        if(k == 0){
                                FOA(i, g[u]){
                                        int v = (u ^ edge[i].fs ^ edge[i].sd);
                                        int w = cost[i];

                                        if(dist[0][v] > dist[0][u] + w){
                                                dist[0][v] = dist[0][u] + w;

                                                add(dist[0][v], 0, v);
                                        }
                                }

                                FOA(v, d1.ing[u]){
                                        if(dist[1][v] > dist[0][u]){
                                                dist[1][v] = dist[0][u];

                                                add(dist[1][v], 1, v);
                                        }
                                }

                                FOA(v, d1.rev[u]){
                                        if(dist[2][v] > dist[0][u]){
                                                dist[2][v] = dist[0][u];

                                                add(dist[2][v], 2, v);
                                        }
                                }
                        }
                        else if(k == 1){
                                FOA(v, d1.ing[u]){
                                        if(dist[1][v] > dist[1][u]){
                                                dist[1][v] = dist[1][u];

                                                add(dist[1][v], 1, v);
                                        }
                                }

                                FOA(i, g[u]){
                                        int v = (edge[i].fs ^ edge[i].sd ^ u);
                                        int w = cost[i];

                                        if(dist[3][v] > dist[1][u] + w){
                                                dist[3][v] = dist[1][u] + w;

                                                add(dist[3][v], 3, v);
                                        }
                                }
                        }
                        else if(k == 2){
                                FOA(v, d1.rev[u]){
                                        if(dist[2][v] > dist[2][u]){
                                                dist[2][v] = dist[2][u];

                                                add(dist[2][v], 2, v);
                                        }
                                }

                                FOA(i, g[u]){
                                        int v = (edge[i].fs ^ edge[i].sd ^ u);
                                        int w = cost[i];

                                        if(dist[3][v] > dist[2][u] + w){
                                                dist[3][v] = dist[2][u] + w;

                                                add(dist[3][v], 3, v);
                                        }
                                }
                        }
                        else{
                                FOA(i, g[u]){
                                        int v = (edge[i].fs ^ edge[i].sd ^ u);
                                        int w = cost[i];

                                        if(dist[3][v] > dist[3][u] + w){
                                                dist[3][v] = dist[3][u] + w;

                                                add(dist[3][v], 3, v);
                                        }
                                }
                        }
                }

                return min({dist[0][en], dist[1][en], dist[2][en], dist[3][en]});
        }
};

signed main(){ quickly
        cin >> n >> m >> s >> t >> st >> en;

        FOR(i, 1, m){
                int u, v, w;
                cin >> u >> v >> w;

                edge[i] = {u, v};
                cost[i] = w;

                g[u].push_back(i);
                g[v].push_back(i);
        }

        d1.start = s;
        d1.shortest();
        d1.build(t);

        cout << Road::Dijkstra();
}

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