Submission #1292989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292989		efeg	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	324 ms	26012 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#define int long long 
#define F first
#define S second 
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define mt make_tuple
#define pqueue priority_queue


typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<iii> viii;
typedef set<int> si;
typedef vector<ii> vii;				
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;

const int MOD = 1e9 + 7;
const int INF = 1e5 + 100; 

int n,m,s,t,u,v; 
vector<vii> adj; 
vi distu,distv;

void djikstra(int basla,vi &dist){
    pqueue<ii,vii,greater<ii>> pq; 
    pq.push({0,basla});

    while (!pq.empty()){
        int d,node; tie(d,node) = pq.top();
        pq.pop(); 
        if (dist[node] != -1) continue;
        dist[node] = d;
    
        for (auto pi : adj[node]){
            int to,w; tie(to,w) = pi;
            if (dist[to] != -1) continue;
            pq.push({d + w,to}); 
        }        
    }
}


int32_t main(){
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--; 

    adj.assign(n + 10,vii());
    distu.assign(n + 10,-1);
    distv.assign(n + 10,-1); 
    for (int i = 0; i < m; i++){
        int u,v,w; cin >> u >> v >> w;
        u--; v--;
        adj[u].eb(v,w);
        adj[v].eb(u,w); 
    } 

    djikstra(u,distu);
    djikstra(v,distv);

    pqueue<iii,vector<iii>,greater<iii>> pq; 
    vi dist(n + 10,1e18); 
    vvi dp(n + 10,vi(2,1e18)); 
   
    auto cal = [&](int start,int end) -> int {
        pq.push({0,start,0});
        while (!pq.empty()){
            int d,node,p; tie(d,node,p) = pq.top(); 
            pq.pop();
            if (dist[node] < d) continue;
            if (d < dist[node]){
                dist[node] = d; 
                dp[node][0] = min(distu[node],dp[p][0]);
                dp[node][1] = min(distv[node],dp[p][1]); 
                for (auto tp : adj[node]){
                    int to,w; tie(to,w) = tp; 
                    if (d + w <= dist[to]) pq.push({d + w,to,node}); 
                }
            }
            else {
                int nw0 = min(distu[node],dp[p][0]), nw1 = min(distv[node],dp[p][1]); 
                
                if (nw0 + nw1 < dp[node][0] + dp[node][1]){
                    dp[node][0] = nw0; 
                    dp[node][1] = nw1; 
                }
            }
        }
        return dp[end][0] + dp[end][1]; 
    }; 
    
    cout << min({distu[v],cal(s,t),cal(t,s)}) << endl; 
    return 0; 
}

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