Submission #782990

#	Time	Username	Problem	Language	Result	Execution time	Memory
782990		borisAngelov	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	306 ms	21108 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 60);

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

struct edge
{
    int to;
    long long w;
};

vector<edge> g[maxn];

long long dist_from_u[maxn];
long long dist_from_v[maxn];

void shortest_path(int source, long long dist[])
{
    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    dist[source] = 0LL;

    priority_queue<pair<long long, int>> pq;
    pq.push(make_pair(0LL, source));

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = -pq.top().first;

        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            long long path = curr + g[node][i].w;
            int to = g[node][i].to;

            if (dist[to] > path)
            {
                dist[to] = path;
                pq.push(make_pair(-path, to));
            }
        }
    }
}

long long dp_u[maxn];
long long dp_v[maxn];

bool visited[maxn];
long long dist[maxn];

long long ans = inf;

void calc_dp(long long source, long long sink)
{
    for (int i = 1; i <= n; ++i)
    {
        visited[i] = false;
        dist[i] = inf;
        dp_u[i] = inf;
        dp_v[i] = inf;
    }

    priority_queue<pair<long long, pair<int, int>>> pq;
    pq.push(make_pair(0LL, make_pair(source, 0)));

    dp_u[0] = inf;
    dp_v[0] = inf;

    while (!pq.empty())
    {
        long long curr = -pq.top().first;
        int node = pq.top().second.first;
        int par = pq.top().second.second;

        pq.pop();

        if (visited[node] == false)
        {
            dist[node] = curr;
            visited[node] = true;

            dp_u[node] = min(dist_from_u[node], dp_u[par]);
            dp_v[node] = min(dist_from_v[node], dp_v[par]);

            for (int i = 0; i < g[node].size(); ++i)
            {
                long long path = curr + g[node][i].w;
                int to = g[node][i].to;

                if (visited[to] == false)
                {
                    pq.push(make_pair(-path, make_pair(to, node)));
                }
            }
        }
        else if (curr == dist[node])
        {
            if (min(dist_from_u[node], dp_u[par]) + min(dist_from_v[node], dp_v[par]) <= dp_u[node] + dp_v[node])
            {
                dp_u[node] = min(dist_from_u[node], dp_u[par]);
                dp_v[node] = min(dist_from_v[node], dp_v[par]);
            }
        }
    }

    ans = min(ans, dp_u[sink] + dp_v[sink]);
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

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

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        long long w;
        cin >> w;

        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    shortest_path(u, dist_from_u);
    shortest_path(v, dist_from_v);

    ans = dist_from_u[v];

    calc_dp(s, t);
    calc_dp(t, s);

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void shortest_path(int, long long int*)':
commuter_pass.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void calc_dp(long long int, long long int)':
commuter_pass.cpp:95:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for (int i = 0; i < g[node].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~

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