Submission #1167650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167650		diana	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	140 ms	18924 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC oprimize("O3, unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define edge pair<ll, int>
#define c first
#define v second
using namespace std;

typedef long long ll;

const int N = 1e5+5;
const ll M = 1e18;
vector<edge> graf[N];
int n, m, s, t, u, v;

ll dfv[N], dfs[N], dft[N];
bool vsv[N], vss[N], vst[N];
void start()
{
    for(int i=0; i<N; i++)
        dfv[i] = M,
        dfs[i] = M,
        dft[i] = M;
}

void dijfromU()
{
    priority_queue<edge, vector<edge>, greater<edge>> pq;
    pq.push({0, v});
    dfv[v] = 0;

    while(!pq.empty())
    {
        edge t = pq.top();  pq.pop();
        if(vsv[t.v])
            continue;
        vsv[t.v] = 1;
        for(auto x: graf[t.v])
        {
            if(t.c + x.c < dfv[x.v])
            {
                pq.push({t.c + x.c, x.v});
                dfv[x.v] = t.c + x.c;
            }
        }
    }
}
void dijfromS()
{
    priority_queue<edge, vector<edge>, greater<edge>> pq;
    pq.push({0, s});
    dfs[s] = 0;

    while(!pq.empty())
    {
        edge t = pq.top();  pq.pop();
        if(vss[t.v])
            continue;
        vss[t.v] = 1;
        for(auto x: graf[t.v])
        {
            if(t.c + x.c < dfs[x.v])
            {
                pq.push({t.c + x.c, x.v});
                dfs[x.v] = t.c + x.c;
            }
        }
    }
}
void dijfromT()
{
    priority_queue<edge, vector<edge>, greater<edge>> pq;
    pq.push({0, t});
    dft[t] = 0;

    while(!pq.empty())
    {
        edge t = pq.top();  pq.pop();
        if(vst[t.v])
            continue;
        vst[t.v] = 1;
        for(auto x: graf[t.v])
        {
            if(t.c + x.c < dft[x.v])
            {
                pq.push({t.c + x.c, x.v});
                dft[x.v] = t.c + x.c;
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    start();

    int n, m; cin >> n >> m >> s >> t >> u >> v;

    while(m--)
    {
        ll a, b, c; cin >> a >> b >> c;
        graf[a].push_back({c, b});
        graf[b].push_back({c, a});
    }

    dijfromT();
    dijfromU();
    dijfromS();

    ll ans = M, d=M;

    for(int i=1; i<=n; i++)
    {
        if(dft[i]+dfs[i]==d)
            ans = min(ans, dfv[i]);
        else if(dft[i]+dfs[i]<d)
            ans = dfv[i],
            d = dft[i]+dfs[i];
    }

    cout << ans;
    return 0;
}

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