제출 #1087082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087082		tdkhai	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	378 ms	71460 KiB

commuter_pass

/*
K stands for "Khongbietcode"
grade 11 computer science
Tran Dai Nghia Highschool for the gifted
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define pb push_back
#define ull unsigned long long
#define llll pair<ll,ll>
#define llllm map<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define X first
#define Y second
#define INF 1LL<<60

using namespace std;
using namespace __gnu_pbds;

const ll N=1e5+1;
vector<llll> a[N],b[N*4];
ll d[2][N],d1[N*4];
ll n,m,s,t,x,y;

void dijkstra(ll id,ll u)
{
    for(int i=1;i<=n;i++)
    {
        d[id][i]=INF;
    }
    d[id][u]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({0,u});
    while(!pq.empty())
    {
        llll top=pq.top();
        pq.pop();
        if(d[id][top.Y]!=top.X)
            continue;
        for(auto v:a[top.Y])
        {
            if(d[id][v.X]>d[id][top.Y]+v.Y)
            {
                pq.push({d[id][v.X]=d[id][top.Y]+v.Y,v.X});
            }
        }
    }
}
void solve(){
    cin >> n >> m >> s >> t >> x >> y;
    for(int i=0;i<m;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        a[u].pb({v,w});
        a[v].pb({u,w});
    }
    dijkstra(0,s);
    dijkstra(1,t);
    for(int u=1;u<=n;u++)
    {
        b[u].pb({n+u,0});
        b[u].pb({2*n+u,0});
        b[n+u].pb({3*n+u,0});
        b[2*n+u].pb({3*n+u,0});
        for(auto i:a[u])
        {
            ll v=i.X,w=i.Y;
            b[u].pb({v,w});
            b[3*n+u].pb({3*n+v,w});
            if(d[0][u]+w+d[1][v]==d[0][t])
            {
                b[n+u].pb({n+v,0});
                b[n*2+v].pb({2*n+u,0});
            }
        }
    }
    for(int i=1;i<=n*4;i++)
    {
        d1[i]=INF;
    }
    priority_queue<llll,vector<llll> ,greater<llll>> pq;
    pq.push({d1[x]=0,x});
    while(pq.size())
    {
        auto top=pq.top();
        pq.pop();
        if(d1[top.Y]!=top.X) continue;
        for(auto i:b[top.Y])
        {
            if(d1[i.X]>d1[top.Y]+i.Y)
            {
                pq.push({d1[i.X]=d1[top.Y]+i.Y,i.X});
            }
        }
    }
    cout << d1[3*n+y];
}
int main(){
    fastIO;
//    freopen("tdk.inp","r",stdin);
//    freopen("tdk.out","w",stdout);
    //freopen("tdk.err","b",stderr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout << endl;
    }
    // cout << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
    return 0;
}

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