Submission #764951

#	Time	Username	Problem	Language	Result	Execution time	Memory
764951		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	379 ms	21264 KiB

commuter_pass

/**
  * Author: Amirrrr
  * Created: 23.06.2023
  * Why am I so stupid? :c
  * Slishkom slab
**/

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define FF first
#define SS second
#define ent "\n"
#define int long long

const int N = 1e5 + 13;
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int maxn = 1e6 + 12;

int n,m,s,t,u,v,ans[N],pr[N],ans1[N];

vector<pair<int,int>>g[N];

void gogo (){
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=1;i<=m;i++){
        int x,y,val;cin>>x>>y>>val;
        g[x].pb({y,val});
        g[y].pb({x,val});
    }
    for(int i=1;i<=n;i++)ans[i]=INF,ans1[i]=INF;
    set<pair<int,int>>st;
    st.insert({0,s});
    set<pair<int,int>>dst;
    ans[s]=0;
    while(st.size()){
        pair<int,int> v=*(st.begin());
        st.erase(st.begin());
        for(auto to:g[v.SS]){
            if(ans[to.FF]>ans[v.SS]+to.SS){
                int cur=ans[v.SS]+to.SS;
                st.erase({ans[to.FF],to.FF});
                ans[to.FF]=cur;
                st.insert({cur,to.FF});
                pr[to.FF]=v.SS;
            }
        }
    }
    int ok=t;
    while(ok){
        dst.insert({ok,pr[ok]});
        ok=pr[ok];
    }
    st.insert({0,u});
    ans1[u]=0;
    while(st.size()){
        pair<int,int> v=*(st.begin());
        st.erase(st.begin());
        for(auto to:g[v.SS]){
            int cur=ans1[v.SS]+to.SS;
            if(dst.count({to.FF,v.SS}))cur=0;
            else if(dst.count({v.SS,to.FF}))cur=0;
            if(ans1[to.FF]>cur){
                st.erase({ans1[to.FF],to.FF});
                ans1[to.FF]=cur;
                st.insert({cur,to.FF});
                pr[to.FF]=v.SS;
            }
        }
    }
    cout<<ans1[v];
}

signed main (/*Amir Mirmanov*/){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int Q=1,test=1;
    //freopen("rain.in","r",stdin);
	//freopen("rain.out","w",stdout);
    //cin>>Q;
    while (Q --){
        gogo();
    }
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:13: warning: unused variable 'test' [-Wunused-variable]
   80 |     int Q=1,test=1;
      |             ^~~~

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