Submission #971478

#	Time	Username	Problem	Language	Result	Execution time	Memory
971478		shezitt	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	103 ms	262144 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;

    vector<vi> d(n+1, vi(n+1, 4e18));

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

    fore(i, 1, n+1){
        d[i][i] = 0;
    }

    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});
                }
            }

        }
    };

    // fore(i, 1, n+1){
    //     dijkstra(i, d[i]);
    // }

    // floyd-warshal
    fore(k, 1, n+1){
        fore(i, 1, n+1){
            fore(j, 1, n+1){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    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]);

            ans = min(ans, res);
            
        }
    }

    cout << ans;

}

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:56:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |             auto [cost, node] = pq.top();
      |                  ^
commuter_pass.cpp:61:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |             for(auto [to, c] : adj[node]){
      |                      ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51:10: warning: variable 'dijkstra' set but not used [-Wunused-but-set-variable]
   51 |     auto dijkstra = [&](int r, vi &dis) -> void {
      |          ^~~~~~~~

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