Submission #854791

#	Time	Username	Problem	Language	Result	Execution time	Memory
854791		hungnt	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	201 ms	26180 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define pii pair<long long, int>
const int N = 1e9 + 7;
using namespace std;
//khai bao
int n, m, s, t, x, y;
vector<pii> ke[100009];
// dijkstra
priority_queue<pii, vector<pii>, greater<pii> > p;
ll f[100009][2];
pair<ll, ll> g[100009];
ll dijkstra(int s, int t, int id){
    while(p.size()) p.pop();
    for(int i = 0; i <= n; i ++)
        f[i][id] = 1e18;
    f[s][id] = 0;
    p.push({0, s});
    while(p.size()){
        pii o = p.top();
        p.pop();
        if(f[o.second][id] != o.first) continue;
        if(o.second == t) return o.first;
        for(pii i : ke[o.second])
            if(f[i.second][id] > o.first + i.first){
                f[i.second][id] = o.first + i.first;
                p.push({f[i.second][id], i.second});
            }
    }
    return 0;
}
/// tinh toan
struct kt{
    ll w, w1, w2, u;
};
struct sx{
    bool operator()(kt a, kt b){
        if(a.w == b.w) return (a.w2 + a.w1) > (b.w2 + b.w1);
        return a.w > b.w;
    }
};
priority_queue<kt, vector<kt>, sx> q;
ll tinh(){
    for(int i = 1; i <= n; i ++)
        g[i] = {1e18, 1e18};
    q.push({0, f[s][0], f[s][1], s});
    g[s] = {0, f[s][0] + f[s][1]};
    while(q.size()){
        kt o = q.top();
//        cout << o.u <<  " " << o.w << " " << o.w1 << " " << o.w2 << '\n';
        q.pop();
        if(o.u == t) return o.w1 + o.w2;
        pair<ll, ll> y;
        y = {o.w, o.w1 + o.w2};
        if(g[o.u] != y) continue;
        for(pii i : ke[o.u]){
            y = {o.w + i.first, min(o.w1, f[i.second][0]) + min(o.w2, f[i.second][1])};
            if(g[i.second] > y){
                g[i.second] = {o.w + i.first, min(o.w1, f[i.second][0]) + min(o.w2, f[i.second][1])};
                q.push({g[i.second].first, min(o.w1, f[i.second][0]), min(o.w2, f[i.second][1]), i.second});
            }
        }
    }
    return 2;
}
/// main mannnnnnnn
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("bus.inp", "r", stdin);
    //freopen("bus.out", "w", stdout);
    cin >> n >> m >> s >> t >> x >> y;
    int u, v, w;
    while(m --){
        cin >> u >> v >> w;
        ke[u].push_back({w, v});
        ke[v].push_back({w, u});
    }
    ll res = dijkstra(x, y, 0);
    ll l = dijkstra(x, 0, 0);
    l = dijkstra(y, 0, 1);
    res = min(res, tinh());
    cout << res;
}
//8 8
//1 6
//3 8
//1 2 3
//2 4 2
//2 3 3
//4 5 3
//3 5 2
//5 6 3
//2 7 4
//8 2 3

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:8: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   80 |     ll l = dijkstra(x, 0, 0);
      |        ^

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