oj.uz

Submission #765462

# Submission time Handle Problem Language Result Execution time Memory
765462 2023-06-24T14:08:43 Z wmuree Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 276 ms 21556 KB 
    /*
Muqalzhar taui
*/
#include <bits/stdc++.h>
#include <iomanip>
 
#define ll long long
#define pb push_back
#define F first
#define S second
#define nl '\n'
#define all(x) x.begin(), x.end()
 
const int N = 2e5 + 7;
const int modd = 1e9 + 7;
const int INF = 1e9 + 7;
const double pi = 3.141592653589793238462643383279502884197;
const double EPS = 0.0000000000001;
using namespace std;
  
int gcd(int a, int b){
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
ll binpow(ll a, ll x){
    if(x == 0) return 1;
    if(x % 2 == 0){
        ll y = binpow(a, x / 2);
        return (y * y);
    }
    else{
        return (binpow(a, x - 1) * a);
    }
}

ll n, m, s, t, u, v;
vector <pair <ll, ll>> e[N];
ll dpu[N];
ll dpv[N];
ll du[N];
ll dv[N];
void Muqaltin(){  
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        e[a].pb({b, c});
        e[b].pb({a, c});
    }
    for(int i = 1; i <= n; i++){
        du[i] = INF;
        dv[i] = INF;
        dpu[i] = INF;
        dpv[i] = INF;
    }
    set <pair <ll, ll>> q;
    dv[t] = 0;
    q.insert({dv[t], t});
    while(!q.empty()){
        ll x = q.begin()->second;
        q.erase(q.begin());

        for(auto to : e[x]){
            if(dv[to.F] > dv[x] + to.S){
                q.erase({dv[to.F], to.F});
                dv[to.F] = dv[x] + to.S;
                q.insert({dv[to.F], to.F});
            }
        }
    }
    du[s] = 0;
    q.insert({du[s], s});
    while(!q.empty()){
        ll x = q.begin()->second;
        q.erase(q.begin());

        for(auto to : e[x]){
            if(du[to.F] > du[x] + to.S){
                q.erase({du[to.F], to.F});
                du[to.F] = du[x] + to.S;
                q.insert({du[to.F], to.F});
            }
        }
    }
    
    set <pair <ll, ll>> st;
    dpu[u] = 0;
    st.insert({dpu[u], u});
    while(!st.empty()){
        ll x = st.begin()->second;
        st.erase(st.begin());

        for(auto to : e[x]){
            if(du[x] + to.S + dv[to.F] != du[t]){
                if(dpu[to.F] > dpu[x] + to.S){
                    st.erase({dpu[to.F], to.F});
                    dpu[to.F] = dpu[x] + to.S;
                    st.insert({dpu[to.F], to.F});
                }
            }
            else{
                if(dpu[to.F] > dpu[x]){
                    st.erase({dpu[to.F], to.F});
                    dpu[to.F] = min(dpu[x], du[to.F]);
                    st.insert({dpu[to.F], to.F});
                }
            }
        }
    }
    cout << dpu[v];
    return;
}
 
int main(){
    // freopen("pails.in", "r", stdin);
    //  freopen("pails.out", "w", stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t = 1;
    // cin >> t;
    while(t--){
        Muqaltin();
    }
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 21472 KB Output is correct
2 Correct 238 ms 20592 KB Output is correct
3 Correct 207 ms 20264 KB Output is correct
4 Correct 239 ms 21496 KB Output is correct
5 Correct 222 ms 20616 KB Output is correct
6 Correct 276 ms 21556 KB Output is correct
7 Correct 239 ms 20300 KB Output is correct
8 Correct 233 ms 20608 KB Output is correct
9 Incorrect 85 ms 18544 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 20776 KB Output is correct
2 Correct 264 ms 20184 KB Output is correct
3 Correct 273 ms 20172 KB Output is correct
4 Incorrect 265 ms 20232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 21472 KB Output is correct
2 Correct 238 ms 20592 KB Output is correct
3 Correct 207 ms 20264 KB Output is correct
4 Correct 239 ms 21496 KB Output is correct
5 Correct 222 ms 20616 KB Output is correct
6 Correct 276 ms 21556 KB Output is correct
7 Correct 239 ms 20300 KB Output is correct
8 Correct 233 ms 20608 KB Output is correct
9 Incorrect 85 ms 18544 KB Output isn't correct
10 Halted 0 ms 0 KB -