Submission #127200

#	Time	Username	Problem	Language	Result	Execution time	Memory
127200		FutymyClone	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	406 ms	17304 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, s, t, s2, t2;
long long d[N], d2[N], d3[N];
vector <pair <int, int> > g[N];
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > pq;

int main(){
    scanf("%d %d", &n, &m);
    scanf("%d %d", &s, &t);
    scanf("%d %d", &s2, &t2);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        g[u].push_back({w, v});
        g[v].push_back({w, u});
    }

    memset(d, 0x3f, sizeof(d));
    d[s] = 0; pq.push({d[s], s});
    while (!pq.empty()) {
        pair <long long, int> val = pq.top(); pq.pop();
        long long dist = val.first;
        int u = val.second;

        if (dist == d[u]) {
            for (auto V: g[u]) {
                int w = V.first, v = V.second;
                if (d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    pq.push({d[v], v});
                }
            }
        }
    }

    memset(d3, 0x3f, sizeof(d3));
    d3[t] = 0; pq.push({d3[t], t});
    while (!pq.empty()) {
        pair <long long, int> val = pq.top(); pq.pop();
        long long dist = val.first;
        int u = val.second;

        if (dist == d3[u]) {
            for (auto V: g[u]) {
                int w = V.first, v = V.second;
                if (d3[v] > d3[u] + w) {
                    d3[v] = d3[u] + w;
                    pq.push({d3[v], v});
                }
            }
        }
    }

    memset(d2, 0x3f, sizeof(d2));
    d2[s2] = 0; pq.push({d2[s2], s2});
    while (!pq.empty()) {
        pair <long long, int> val = pq.top(); pq.pop();
        long long dist = val.first;
        int u = val.second;

        if (dist == d2[u]) {
            for (auto V: g[u]) {
                int v = V.second;
                int w = (d[u] + d3[v] + V.first == d[t] || d[v] + d3[u] + V.first == d[t] ? 0 : V.first);
                if (d2[v] > d2[u] + w) {
                    d2[v] = d2[u] + w;
                    pq.push({d2[v], v});
                }
            }
        }
    }

    printf("%lld", d2[t2]);
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &s, &t);
     ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &s2, &t2);
     ~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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