Submission #963074

#	Time	Username	Problem	Language	Result	Execution time	Memory
963074		toast12	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	343 ms	17956 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15;

int n, m;
vector<vector<pair<int, int>>> adj;

void dijkstras(vector<int> &parent, vector<long long> &dist, int start) {
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        for (auto e : adj[x]) {
            int w = e.second;
            if (w + dist[x] < dist[e.first]) {
                parent[e.first] = x;
                dist[e.first] = dist[x]+w;
                pq.push({-dist[e.first], e.first});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    adj.resize(n+1);
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    vector<int> p(n+1);
    p[s] = s;
    vector<long long> d(n+1, INF);
    d[s] = 0;
    dijkstras(p, d, s);
    vector<int> path;
    int x = t;
    while (x != s) {
        path.push_back(x);
        x = p[x];
    }
    path.push_back(s);
    vector<int> from_u(n+1);
    vector<long long> du(n+1, INF);
    du[u] = 0;
    dijkstras(from_u, du, u);
    vector<int> from_v(n+1);
    vector<long long> dv(n+1, INF);
    dv[v] = 0;
    dijkstras(from_v, dv, v);
    long long ans = du[v];
    long long mnu = INF, mnv = INF;
    for (int i = 0; i < path.size(); i++) {
        mnu = min(mnu, du[path[i]]);
        mnv = min(mnv, dv[path[i]]);
        ans = min(ans, mnu+mnv);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < path.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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