Submission #971475

#	Time	Username	Problem	Language	Result	Execution time	Memory
971475		shezitt	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	45 ms	4444 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <queue>
#include <set>

using namespace std;

using ll = long long;

#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define ii pair<int,int>
#define F first
#define S second

const int MAXN = 1010;

vector<ii> adj[MAXN];

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

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    fore(i, 0, m){
        int x, y, c;
        cin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }

    auto dijkstra = [&](int r, vi &dis) -> void {
        dis[r] = 0;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push({0, r});
        while(sz(pq)){
            auto [cost, node] = pq.top();
            pq.pop();

            if(cost != dis[node]) continue;

            for(auto [to, c] : adj[node]){
                if(dis[node] + c < dis[to]){
                    dis[to] = dis[node] + c;
                    pq.push({dis[to], to});
                }
            }

        }
    };

    vector<vi> d(n+1, vi(n+1, 4e18));
    fore(i, 1, n+1){
        dijkstra(i, d[i]);
    }

    int ans = d[u][v];

    fore(xx, 1, n+1){
        fore(yy, 1, n+1){
            int x = xx, y = yy;

            if(d[s][y] < d[s][x]) swap(x, y);

            if(d[s][x] + d[x][y] != d[s][y]) continue;
            if(d[s][x] + d[x][y] + d[y][t] != d[s][t]) continue;

            int res = min(d[u][x] + d[v][y], d[v][x] + d[u][y]);

            if(res == 14) {
                cerr << x << ' ' << y << endl;
            }

            ans = min(ans, res);
            
        }
    }

    cout << ans;

}

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |             auto [cost, node] = pq.top();
      |                  ^
commuter_pass.cpp:54:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |             for(auto [to, c] : adj[node]){
      |                      ^

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