Submission #851775

#	Time	Username	Problem	Language	Result	Execution time	Memory
851775		chautanphat	Commuter Pass (JOI18_commuter_pass)	C++14	40 / 100	186 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+1;
int n;
vector< pair<long long, int> > a[maxn];

vector<long long> dijkstra(int start)
{
    vector<long long> d(n+1, 1e16);
    d[start] = 0;
    priority_queue< pair<long long, int> > q;
    q.push(make_pair(0, start));
    vector<bool> vs(n+1);
    while (q.size())
    {
        int u = q.top().second;
        q.pop();
        if (vs[u]) continue;
        vs[u] = 1;

        for (int i = 0; i < (int)a[u].size(); i++)
        {
            int v = a[u][i].first, w = a[u][i].second;
            if (d[u]+w < d[v])
            {
                d[v] = d[u]+w;
                q.push(make_pair(-d[v], v));
            }
        }
    }

    return d;
}

int main()
{    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back(make_pair(v, w));
        a[v].push_back(make_pair(u, w));
    }

    if (s == u)
    {
        long long ans = 1e16;
        vector<long long> ds, dt, dv;
        ds = dijkstra(s), dt = dijkstra(t), dv = dijkstra(v);
        for (int i = 1; i <= n; i++)
            if (ds[i]+dt[i] == ds[t]) ans = min(ans, dv[i]);
        cout << ans;
        return 0;
    }

    vector< vector<long long> > d(n+1, vector<long long> (n+1, 1e16));
    for (int i = 1; i <= n; i++)
    {
        d[i][i] = 0;
        for (int j = 0; j < (int)a[i].size(); j++)
            d[i][a[i][j].first] = a[i][j].second;
    }

    for (int k = 1; k <= n; k++)
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++)
                d[u][v] = min(d[u][v], d[u][k]+d[k][v]);

    long long ans = 1e16;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[s][i]+d[i][j]+d[j][t] == d[s][t])
                ans = min(ans, min(d[u][i]+d[j][v], d[u][j]+d[i][v]));
    cout << min(ans, d[u][v]);
    return 0;
}

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