oj.uz

Submission #782990

# Submission time Handle Problem Language Result Execution time Memory
782990 2023-07-14T13:47:14 Z borisAngelov Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 306 ms 21108 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21048 KB Output is correct
2 Correct 240 ms 20584 KB Output is correct
3 Correct 269 ms 20716 KB Output is correct
4 Correct 276 ms 20856 KB Output is correct
5 Correct 267 ms 20544 KB Output is correct
6 Correct 248 ms 21108 KB Output is correct
7 Correct 234 ms 20616 KB Output is correct
8 Correct 248 ms 20528 KB Output is correct
9 Correct 285 ms 20788 KB Output is correct
10 Correct 231 ms 20628 KB Output is correct
11 Correct 80 ms 12108 KB Output is correct
12 Correct 306 ms 20796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 20804 KB Output is correct
2 Correct 242 ms 20456 KB Output is correct
3 Correct 267 ms 20364 KB Output is correct
4 Correct 266 ms 20368 KB Output is correct
5 Correct 247 ms 20420 KB Output is correct
6 Correct 250 ms 20664 KB Output is correct
7 Correct 246 ms 20348 KB Output is correct
8 Correct 237 ms 20424 KB Output is correct
9 Correct 267 ms 20332 KB Output is correct
10 Correct 253 ms 20412 KB Output is correct
11 Correct 73 ms 12072 KB Output is correct
12 Correct 280 ms 20732 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4732 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 25 ms 6624 KB Output is correct
5 Correct 13 ms 5104 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2948 KB Output is correct
9 Correct 2 ms 2820 KB Output is correct
10 Correct 12 ms 4748 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2680 KB Output is correct
13 Correct 2 ms 2684 KB Output is correct
14 Correct 2 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 21048 KB Output is correct
2 Correct 240 ms 20584 KB Output is correct
3 Correct 269 ms 20716 KB Output is correct
4 Correct 276 ms 20856 KB Output is correct
5 Correct 267 ms 20544 KB Output is correct
6 Correct 248 ms 21108 KB Output is correct
7 Correct 234 ms 20616 KB Output is correct
8 Correct 248 ms 20528 KB Output is correct
9 Correct 285 ms 20788 KB Output is correct
10 Correct 231 ms 20628 KB Output is correct
11 Correct 80 ms 12108 KB Output is correct
12 Correct 306 ms 20796 KB Output is correct
13 Correct 238 ms 20804 KB Output is correct
14 Correct 242 ms 20456 KB Output is correct
15 Correct 267 ms 20364 KB Output is correct
16 Correct 266 ms 20368 KB Output is correct
17 Correct 247 ms 20420 KB Output is correct
18 Correct 250 ms 20664 KB Output is correct
19 Correct 246 ms 20348 KB Output is correct
20 Correct 237 ms 20424 KB Output is correct
21 Correct 267 ms 20332 KB Output is correct
22 Correct 253 ms 20412 KB Output is correct
23 Correct 73 ms 12072 KB Output is correct
24 Correct 280 ms 20732 KB Output is correct
25 Correct 13 ms 4732 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 25 ms 6624 KB Output is correct
29 Correct 13 ms 5104 KB Output is correct
30 Correct 2 ms 2816 KB Output is correct
31 Correct 3 ms 2900 KB Output is correct
32 Correct 3 ms 2948 KB Output is correct
33 Correct 2 ms 2820 KB Output is correct
34 Correct 12 ms 4748 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct
36 Correct 2 ms 2680 KB Output is correct
37 Correct 2 ms 2684 KB Output is correct
38 Correct 2 ms 2772 KB Output is correct
39 Correct 2 ms 2772 KB Output is correct
40 Correct 234 ms 20320 KB Output is correct
41 Correct 268 ms 20808 KB Output is correct
42 Correct 273 ms 20728 KB Output is correct
43 Correct 72 ms 12144 KB Output is correct
44 Correct 106 ms 12156 KB Output is correct
45 Correct 221 ms 19064 KB Output is correct
46 Correct 214 ms 19016 KB Output is correct
47 Correct 252 ms 20904 KB Output is correct
48 Correct 71 ms 12116 KB Output is correct
49 Correct 229 ms 20204 KB Output is correct
50 Correct 223 ms 19256 KB Output is correct
51 Correct 276 ms 19120 KB Output is correct