Submission #838908

#	Time	Username	Problem	Language	Result	Execution time	Memory
838908		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	267 ms	25368 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const int nx=1e5+5;
int n, m, s, t, u, v, out[nx];
ll dp[nx], d[nx][5], kq=inf;
pair<ll, ll> a[nx];
vector<int> topo;
struct dak
{
    int v;
    ll w;
    bool operator <(const dak &o)
    const
    {
        return w>o.w;
    }
};
priority_queue<dak> f;
vector<dak> adj[nx];
void find(int u, int k)
{
    d[u][k]=0;
    f.push({u, d[u][k]});
    while(f.size())
    {
        dak v=f.top();
        f.pop();
        if(d[v.v][k]<v.w)
            continue;
        for(auto it:adj[v.v])
        {
            if(d[it.v][k]>d[v.v][k]+it.w)
            {
                d[it.v][k]=d[v.v][k]+it.w;
                f.push({it.v, d[it.v][k]});
            }
        }
    }
}
bool cmp(pair<ll, ll> a, pair<ll, ll> b)
{
    return a.fi>b.fi;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>s>>t>>u>>v;
    while(m--)
    {
        int a, b;
        ll c;
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    memset(d, 0x3f, sizeof(d));
    memset(dp, 0x3f, sizeof(dp));
    find(s, 0);
    find(t, 1);
    find(u, 2);
    find(v, 3);
    for(int i = 1; i <= n; i++)
        a[i]=make_pair(d[i][0], i);
    sort(a+1, a+n+1, cmp);
    for(int i = 1; i <= n; i++)
        topo.emplace_back(a[i].se);
    for(int u:topo)
    {
        if(d[u][0]+d[u][1]==d[t][0])
        {
            for(auto v:adj[u])
            {
                if(d[u][0]+v.w==d[v.v][0])
                    dp[u]=min({dp[u], dp[v.v], d[u][3]});
            }
        }
    }
    for(int i = 1; i <= n; i++)
        kq=min(kq, d[i][2]+dp[i]);
    memset(dp, 0x3f, sizeof(dp));
    for(int u:topo)
    {
        if(d[u][0]+d[u][1]==d[t][0])
        {
            for(auto v:adj[u])
            {
                if(d[u][0]+v.w==d[v.v][0])
                    dp[u]=min({dp[u], dp[v.v], d[u][2]});
            }
        }
    }
    for(int i = 1; i <= n; i++)
        kq=min(kq, d[i][3]+dp[i]);
    cout<<kq;
}

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