Submission #1144396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144396		tnt	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	219 ms	26384 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back                    
#define ll long long
#define int long long
//#define sort(all(v)) sort(v.begin(),v.end())

int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 1e9;
int fact[200001];
ll binpow(ll a, ll b){
 if(b == 0) return 1;
 else if(b % 2 == 1) return (a * binpow(a, b - 1)) % mod;
 ll p = binpow(a,b / 2);
 return (p * p) % mod;
}
map <pair<int,int>,bool> mp;
vector <pair<int,int>> g[N],g1[N];
signed main(){
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    int n,m;
    cin >> n >> m;
    int s,t;
    cin >> s >> t;
    int u,v;
    cin >> u >> v;
    vector <array<int,3>> q1;
    for(int i = 1; i <= n; i++){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].pb({b,c});
        g[b].pb({a,c});
        q1.pb({a,b,c});
    }
    vector <int> d(n + 1,1e18),p(n + 1);
    set <pair<int,int>> st;
    st.insert({0,s});
    d[s] = 0;
    while(st.size() > 0){
        int u1 = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to,w] : g[u1]){
            if(d[to] > d[u1] + w){
                st.erase({d[to],to});
                d[to] = d[u1] + w;
                p[to] = u1;
                st.insert({d[to],to});
            }
        }
    }
    queue <int> q;
    vector <int> bag;
    q.push(s);
    bag.pb(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(p[u] != 0){
            q.push(p[u]);
            bag.pb(p[u]);
        }
    }
    reverse(bag.begin(),bag.end());
    for(int i = 0; i < bag.size() - 1; i++){
        mp[{bag[i],bag[i + 1]}] = 1;
    }
    for(int i = 0; i < n; i++){
        int a = q1[i][0],b = q1[i][1],c = q1[i][2];
        if(mp[{a,b}] != 1){
            g1[a].pb({b,c});
            g1[b].pb({a,c});
        }  
    }
    for(int i = 1; i <= n; i++) d[i] = 1e18;
    st.insert({0,u});
    d[u] = 0;
    while(st.size() > 0){
        int u1 = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to,w] : g[u1]){
            if(d[to] > d[u1] + w){
                st.erase({d[to],to});
                d[to] = d[u1] + w;
                p[to] = u1;
                st.insert({d[to],to});
            }
        }
    }
    cout << d[v];
    
}

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