Submission #1254458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254458		hitsuuj	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	858 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define inf 1e18
#define ti tuple<int,int,int>
#define meekucaon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
int sf(int a){return (a+mod)%mod;}
int kal(int a,int b){return (sf(a)*sf(b))%mod;}
int tam(int a,int b){return (sf(a)+sf(b))%mod;}
int kur(int a,int b){return (sf(a)+mod-sf(b))%mod;}
const int lim=100000;
vector<pii>g[lim+10];
vector<int>diss,dist,disv,disa,disb;
int n,m,s,t,a,b;
vector<int> cari(int aw){
    priority_queue<pii,vector<pii>,greater<pii>>q;
    vector<int>disc(n+10,inf);
    disc[aw]=0;
    q.push({0,aw});
    while(q.size()){
        auto [dis,u]=q.top();
        q.pop();
        if(disc[u]<dis) continue;
        for(auto [v,w]:g[u]){
            if(disc[v]<=dis+w) continue;
            disc[v]=dis+w;
            q.push({disc[v],v});
        }
    }
    return disc;
}
signed main(){
    meekucaon
    cin>>n>>m>>s>>t>>a>>b;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    disa=cari(a);
    disb=cari(b);
    diss=cari(s);
    dist=cari(t);
    vector<int>mas(n+1,inf),kel(n+1,inf),vis(n+1);
    vector<pii>kelmas(n+1);
    vector<set<int>>col[n+1];
    for(int i=1;i<=n;i++) mas[i]=disa[i];
    for(int i=1;i<=n;i++) kel[i]=disb[i];
    int st=diss[t];
    queue<pair<int,set<int>>>q;
    set<int>cur;
    cur.insert(s);
    q.push({s,cur});
    while(q.size()){
        auto [u,vec]=q.front();
        q.pop();
        vis[u]=1;
        for(auto [v,w]:g[u]){
            bool yes=0;
            if(vec.find(v)!=vec.end())continue;
            if(diss[u]+w==diss[v] && dist[v]+w==dist[u]) yes=1;
            if(yes){
                vec.insert(v);
                // cout<<u<<' '<<v<<endl;
                // for(auto x:vec) cout<<x<<' ';
                // cout<<endl<<endl;
                col[v].pb(vec);
                q.push({v,vec});
                vec.erase(v);
            }
        }
    }
    int ans=inf;
    for(auto x:col[t]){
        int kelo=inf,melo=inf;
        for(auto y:x){
            kelo=min(kelo,kel[y]);
            melo=min(melo,mas[y]);
        }
        ans=min(ans,kelo+melo);
        // cout<<endl;
    }
    cout<<ans;

}

// cari shortest path dari s dan t 
// cari minimum fare dari a ke b 


// known stuff 
// 1. kita bisa cek edge ini masuk shortest route or not
// 2. dari semua yang kita ketahui -> minimum spanning tree dari u ke v?
// 3. harus tau shortest route mana yang dipakai untuk s ke t
// 4. mending pick route yang mana 
// 5. kalau satu arah tinggal cek dikurangin shortest route yang ada 

// subsoal 
// 1. kalau masuk dalam shortest path = weight 0 

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