Submission #335578

#	Time	Username	Problem	Language	Result	Execution time	Memory
335578		Joshc	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	439 ms	27696 KiB

commuter_pass

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define f first
#define s second
#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>

const int MAX_N = 100001;
long long dists[MAX_N], distt[MAX_N], distu[MAX_N], distv[MAX_N], dp[MAX_N], dp2[MAX_N], res = 1e18;
vector<pii> edges[MAX_N];
vector<int> bef[MAX_N], bef2[MAX_N];

void dijkstra(int s, ll dist[]) {
    for (int i=0; i<MAX_N; i++) dist[i] = 1e18;
    dist[s] = 0;
    priority_queue<pli, vector<pli>, greater<pli> > pq;
    pq.push({0, s});
    while (!pq.empty()) {
        pli cur = pq.top();
        pq.pop();
        if (cur.f > dist[cur.s]) continue;
        for (pii p : edges[cur.s]) {
            if (dist[p.f] > dist[cur.s]+p.s) {
                dist[p.f] = dist[cur.s]+p.s;
                pq.push({dist[p.f], p.f});
            }
        }
    }
}

ll ans(int x, vector<int> bef[], ll dp[]) {
    if (dp[x] != 1e18) return dp[x];
    dp[x]--;
    for (int p : bef[x]) dp[x] = min(dp[x], ans(p, bef, dp));
    return dp[x] = min(dp[x], distu[x]);
}

int main() {
    int n, m, s, t, u, v, a, b, c;
    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
    while (m--) {
        scanf("%d%d%d", &a, &b, &c);
        edges[a].emplace_back(b, c);
        edges[b].emplace_back(a, c);
    }
    dijkstra(s, dists);
    dijkstra(t, distt);
    dijkstra(u, distu);
    dijkstra(v, distv);
    for (int i=1; i<=n; i++) {
        for (pii j : edges[i]) {
            if (dists[i]+j.s+distt[j.f] == dists[t]) {
                bef[j.f].push_back(i);
                bef2[i].push_back(j.f);
            }
        }
        dp[i] = dp2[i] = 1e18;
    }
    for (int i=1; i<=n; i++) {
        if (dists[i]+distt[i]==dists[t]) {
            res = min(res, min(ans(i, bef, dp), ans(i, bef2, dp2))+distv[i]);
        }
    }
    printf("%lld\n", min(res, distu[v]));
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d%d%d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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