Submission #898184

#	Time	Username	Problem	Language	Result	Execution time	Memory
898184		andrei_iorgulescu	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1871 ms	27908 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;
const int bulan = 9;

int n,m,s,t,u,v;
vector<pair<int,int>>g[100005];
vector<int>ds,dt,du,dv,dx;

vector<int> dijkstra(int sursa)
{
    vector<int>dist(n + 1);
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    priority_queue<pair<int,int>>pq;
    pq.push({0,sursa});
    while (!pq.empty())
    {
        int nod = pq.top().second,cost = -pq.top().first;
        pq.pop();
        if (dist[nod] == inf)
        {
            dist[nod] = cost;
            for (auto vecin : g[nod])
                pq.push({-(cost + vecin.second),vecin.first});
        }
    }
    return dist;
}

bool cmpu(int A,int B)
{
    return du[A] < du[B];
}

bool cmpv(int A,int B)
{
    return dv[A] < dv[B];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    ds = dijkstra(s);
    dt = dijkstra(t);
    du = dijkstra(u);
    dv = dijkstra(v);
    vector<int>good_nodes;
    for (int i = 1; i <= n; i++)
    {
        if (ds[i] + dt[i] == ds[t])
            good_nodes.push_back(i);
    }
    int ans = du[v];
    sort(good_nodes.begin(),good_nodes.end(),cmpu);
    for (int i = 0; i < min(bulan,(int)good_nodes.size()); i++)
    {
        int x = good_nodes[i];
        dx = dijkstra(x);
        for (int j = 1; j <= n; j++)
        {
            if (ds[x] + dx[j] + dt[j] == ds[t] or ds[j] + dx[j] + dx[t] == ds[t])
                ans = min(ans,dv[j] + du[x]);
        }
    }
    sort(good_nodes.begin(),good_nodes.end(),cmpv);
    for (int i = 0; i < min(bulan,(int)good_nodes.size()); i++)
    {
        int x = good_nodes[i];
        dx = dijkstra(x);
        for (int j = 1; j <= n; j++)
        {
            if (ds[x] + dx[j] + dt[j] == ds[t] or ds[j] + dx[j] + dx[t] == ds[t])
                ans = min(ans,dv[x] + du[j]);
        }
    }
    cout << ans;
    return 0;
}

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