Submission #750962

#	Time	Username	Problem	Language	Result	Execution time	Memory
750962		nonono	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	395 ms	40776 KiB

commuter_pass

#include "bits/stdc++.h"
#define int long long
using namespace std;

const int inf = 1e18;
const int mxN = 1e5 + 10;

int n, m, s, t, U, V;
vector<vector<pair<int, int>>> adj(mxN);
vector<vector<int>> d(5, vector<int> (mxN));

void SP(int type, int x){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for(int i = 1; i <= n; i ++){
        d[type][i] = inf;
    }

    d[type][x] = 0;
    pq.push({0, x});

    while(!pq.empty()){
        int du = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(d[type][u] != du) continue ;

        for(auto [v, w] : adj[u]){
            if(d[type][v] > du + w){
                d[type][v] = du + w;
                pq.push({d[type][v], v});
            }
        }
    }
}

int Res;
int check[mxN], mark[mxN];
int M1[mxN], M2[mxN];
vector<vector<int>> k(mxN);

void dfs(int u){
    check[u] = 1;
    M1[u] = d[1][u];
    M2[u] = d[2][u];

    for(int v : k[u]){
        if(check[v] == 0) dfs(v);
        if(mark[v] == 1){
            mark[u] = 1;
            M1[u] = min(M1[u], M1[v]);
            M2[u] = min(M2[u], M2[v]);
        }
    }

    Res = min({Res, d[1][u] + M2[u], d[2][u] + M1[u]});
}

signed main(){

    #define name "test"
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s >> t >> U >> V;

    vector<array<int, 3>> edges;

    for(int i = 1; i <= m; i ++){
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});

        edges.push_back({u, v, w});
    }

    SP(0, s);
    SP(1, U);
    SP(2, V);

    for(auto [u, v, w] : edges){
        if(d[0][u] + w == d[0][v]) k[u].push_back(v);
        if(d[0][v] + w == d[0][u]) k[v].push_back(u);
    }

    mark[t] = 1;
    for(int i = 1; i <= n; i ++){
        M1[i] = M2[i] = inf;
    }

    Res = d[1][V];
    dfs(s);

    cout << Res << "\n";
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void SP(long long int, long long int)':
commuter_pass.cpp:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         for(auto [v, w] : adj[u]){
      |                  ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for(auto [u, v, w] : edges){
      |              ^
commuter_pass.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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