제출 #834116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834116		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	385 ms	262144 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define int unsigned long long
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
const int mod = LLONG_MAX;
const int maxn = 2e5 + 10;

int n, m, s, t, u, v;
vector<pair<int, int>> adj[maxn];
vector<vector<int>> jalan;


void cari(int node, vector<int>& jalann, vector<int> parent[]){
    if(node == 0){
        jalan.pb(jalann);
        return;
    }

    for(int par : parent[node]){
        //cout << par << " par" << endl;
        jalann.pb(node);
        cari(par, jalann, parent);
        jalann.pop_back();
    }
}
 
int32_t main()
{
    IOS
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    for(int i = 1; i <= m; i++){
        int a, b, c; cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    //pertama cari shortest path untuk dari s ke t
    //problem = bgmn kalau ada lbh dari 1 path dan jaraknya sama
    vector<int> d(n + 5, mod);
    vector<int> p(n + 5, -1);
    //vector<int> vis(n + 1, 0);
    //vector<int> jalan[n + 1];
    vector<int> parent[n + 5];
    
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    parent[s] = {0};
    while(!q.empty()){
        int v = q.top().se;
        int vd = q.top().fi;
        q.pop();
        //cout << v << " v" << endl;
        if(vd != d[v])continue;

        for(auto i : adj[v]){
            int to = i.fi;
            int val = i.se;
            //if(vis[to]) continue;
            if(d[v] + val < d[to]){
                d[to] = d[v] + val;
                p[to] = v;
                q.push({d[to], to});
                parent[to].clear();
                parent[to].pb(v);
            }else if(d[v] + val == d[to]){
                parent[to].pb(v);
            }
        }
    }
    
    vector<int> jalann;
    cari(t, jalann, parent);

    // for(auto i : jalan){
    //     reverse(i.begin(), i.end());
    //     for(auto j : i){
    //         cout << j << " ";
    //     }cout << endl;
    // }
    //we found multiple path
    
    // vector<int> path;
    
    // for(int i = t; i != s; i = p[i]){
    //     path.pb(i);
    // }
    // path.pb(s);
    // reverse(path.begin(), path.end());
    // for(auto i : path){
    //     cout << i << " ";
    // }cout << endl;

    // for(int i = 1; i < path.size(); i++){
    //     tanda[{path[i], path[i - 1]}] = true;
    //     tanda[{path[i - 1], path[i]}] = true;
    // }
    // for(auto i : tanda){
    //     cout << i << " ";
    // }cout << endl;
    int mini = LLONG_MAX;
    for(auto i : jalan){
        vector<int> d1(n + 5, mod);
        //vector<int> vis1(n + 1, 0);
        //vector<int> p1(n + 1, -1);
        map<pair<int, int>, bool> tanda;

        reverse(i.begin(), i.end());
        // for(auto j : i){
        //     cout << j << " ";
        // }cout << endl;
        for(int j = 1; j < i.size(); j++){
            tanda[{i[j], i[j - 1]}] = true;
            tanda[{i[j - 1], i[j]}] = true;  
            //cout << i[j - 1] << " " << i[j] << endl;  
        }

        d1[u] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1;
        q1.push({0, u});
        while(!q1.empty()){
            int v = q1.top().se;
            int vd = q1.top().fi;
            q1.pop();
            //cout << v << " v" << endl;
            if(vd != d1[v])continue;

            for(auto i : adj[v]){
                int to = i.fi;
                int val = i.se;
                //cout << "val = " << val << endl;
                if(tanda[{v, to}]){
                    val = 0;
                    //cout << v << " " << to << endl;
                } 
                if(d1[v] + val < d1[to]){
                    d1[to] = d1[v] + val;
                    //cout << d1[to] << endl;
                    //p1[to] = v;
                    //cout << "p1[" << to << "] = " << p1[to] << endl;
                    q1.push({d1[to], to});
                }
            }
        }
        
        
        // vector<int> ans;
        // for(int j = v; j != u; j = p1[j]){
        //     cout << "j = " << j << endl;
        //     ans.pb(j);
        // }ans.pb(u);
        // reverse(ans.begin(), ans.end());
        // for(auto j : ans){
        //     cout << j << " ";
        // }cout << endl;
        // cout << "d1[v] = " << d1[v] << endl;
        mini = min(mini, d1[v]);
    }

    cout << mini << endl;

    
}

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