Submission #1019453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019453		Kodik	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	201 ms	33496 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
#define int ll
int mod = 1e9+7;
// int inf = 1e18;
 
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ifstream cin ("shortcut.in");
    // ofstream cout ("shortcut.out");
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    --s; --t; --u; --v;
    vector<pair<int,int>> adj[n];
    for(int i = 0; i < m; ++i){
        int a,b,c;
        cin >> a >> b >> c;
        --a; --b;
        adj[a].push_back({c,b});
        adj[b].push_back({c,a});
    }
    vector<int> dis(n, 1e18);
    dis[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<set<int>> par(n);
    pq.push({0, s});
    while(!pq.empty()){
        pair<int,int> a = pq.top(); pq.pop();
        if(dis[a.ss]!=a.ff){
            continue;
        }
        for(auto &[w, nxt] : adj[a.ss]){
            if(a.ff+w<dis[nxt]){
                if(par[nxt].size()) par[nxt].clear();
                par[nxt].insert(a.ss);
                pq.push({a.ff+w, nxt});
                dis[nxt] = a.ff+w;
            }else if(a.ff+w==dis[nxt]){
                par[nxt].insert(a.ss);
            }
        }
    }
    vector<bool> ways(n, false);
    vector<bool> check(n, false);
    queue<int> q;
    q.push({t}); 
    check[t] = true;
    while(!q.empty()){
        int a = q.front(); q.pop();
        ways[a] = true;
        for(int i : par[a]){
            if(!check[i]){
                q.push(i);
                check[i] = true;
            }
        }
    }
    vector<int> how_many(n , 0);
    for(int i = 0; i < n; ++i){
        if(ways[i]){
            for(int j : par[i]){
                how_many[j]++;
            }
        }
    }
    using te = pair<int,pair<int,pair<bool,int>>>;
    priority_queue<te, vector<te>, greater<te>> ppq;
    ppq.push({0,{u,{0,0}}});
    dis.assign(n, 1e18);
    dis[u] = 0;
    while(!ppq.empty()){
        int weight = ppq.top().ff;
        int node = ppq.top().ss.ff;
        bool go = ppq.top().ss.ss.ff;
        int only_forward = ppq.top().ss.ss.ss;
        ppq.pop();
        if(dis[node]!=weight){
            continue;
        }
        // i should remember how i got to node as a child -> can go only to parent 2
        // as a parent can go only go to children 1 
        // 1 if i am not parent of the next node skip
        // 2 if the next node isnt my parent skip 
        for(auto &[w, nxt] : adj[node]){
            if(!go&&ways[node]&&ways[nxt]&&weight<dis[nxt]){
                if((only_forward==1&&par[nxt].count(node)==0)||(only_forward==2&&par[node].count(nxt)==0)){
                    //nothing just didn't want everything to negate
                }else{
                    dis[nxt] = weight;
                    ppq.push({weight,{nxt,{nxt==s||nxt==t, par[node].count(nxt)==0?1:2}}});
                }
            }
            if(weight+w<dis[nxt]){
                dis[nxt] = weight+w;
                ppq.push({weight+w,{nxt,{go,only_forward}}});
            }
        }
    }
    cout << dis[v] << '\n';
 
 
    return 0;   
}

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