oj.uz

답안 #575001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
575001 2022-06-09T13:56:42 Z ac2hu Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 551 ms 45656 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n, m;cin >> n >> m;
    int s, t;cin >> s >> t; --s;--t;
    int u, v;cin >> u >> v; --u;--v;
    vector<array<int, 3>> fake_edg(m);
    vector<vector<pair<int, int>>> fake_adj(n);
    for(auto &[a, b, c] : fake_edg){
        cin >> a >> b >> c;
        --a;--b;
        fake_adj[a].push_back({b, c});
        fake_adj[b].push_back({a, c});
    }
    set<pair<int,int>> selected_edges;/*{{{*/
    priority_queue<pair<int,int>> pq;
    vector<int> fake_dist(n, 1e18);
    fake_dist[s] = 0;
    pq.push({-fake_dist[s], s});
    while(!pq.empty()){
        auto [dd, x] = pq.top();
        dd = -dd;
        pq.pop();
        if(fake_dist[x] != dd)continue;
        for(auto [e, w] : fake_adj[x]){
            if(fake_dist[e] > fake_dist[x] + w){
                fake_dist[e] = fake_dist[x] + w;
                pq.push({-fake_dist[e], e});
            }
        }
    }
    vector<vector<int>> temp_adj(n);
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto [e, w] : fake_adj[x]){
            if(fake_dist[e] == fake_dist[x] + w){
                temp_adj[e].push_back(x);
                if(!visited[e]){
                    visited[e] = true;
                    q.push(e);
                }
            }
        }
    }
    deb(temp_adj);
    fill(visited.begin(), visited.end(), false);
    q.push(t);
    visited[t] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int e : temp_adj[x]){
            selected_edges.insert({min(e, x), max(e, x)});
            if(!visited[e]){
                visited[e]  = true;
                q.push(e);
            }
        }
    }
    deb(selected_edges);
    vector<vector<pair<int,int>>> adj(n);
    for(auto [a, b, c] : fake_edg){
        if(a > b)swap(a, b);
        if(selected_edges.find({a, b}) != selected_edges.end()){
            if(fake_dist[a] < fake_dist[b]){
                deb(a, b);
                adj[a].push_back({b, 0});
                adj[b].push_back({a, c});
            }
            else{
                deb(b, a);
                adj[b].push_back({a, 0});
                adj[a].push_back({b, c});
            }
        }
        else{
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
        }
    }
    deb(adj);
    vector<int> dist(n, 1e18);
    dist[u] = 0;
    pq.push({-dist[u], u});
    while(!pq.empty()){
        auto [dd, x] = pq.top();
        pq.pop();
        dd = -dd;
        if(dist[x] != dd)continue;
        for(auto [e, w] : adj[x]){
            if(dist[e] > dist[x] + w){
                dist[e] = dist[x] + w;
                pq.push({-dist[e], e});
            }
        }
    }
    int ans = dist[v];
    adj.clear();
    adj.resize(n);
    for(auto [a, b, c] : fake_edg){/*{{{*/
        if(a > b)swap(a, b);
        if(selected_edges.find({a, b}) != selected_edges.end()){
            if(fake_dist[a] > fake_dist[b]){
                deb(a, b);
                adj[a].push_back({b, 0});
                adj[b].push_back({a, c});
            }
            else{
                deb(b, a);
                adj[b].push_back({a, 0});
                adj[a].push_back({b, c});
            }
        }
        else{
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
        }
    }
    fill(dist.begin(), dist.end(), 1e18);
    dist[u] = 0;
    pq.push({-dist[u], u});
    while(!pq.empty()){
        auto [dd, x] = pq.top();
        pq.pop();
        dd = -dd;
        if(dist[x] != dd)continue;
        for(auto [e, w] : adj[x]){
            if(dist[e] > dist[x] + w){
                dist[e] = dist[x] + w;
                pq.push({-dist[e], e});
            }
        }
    }
    ans = min(ans, dist[v]);
    cout << ans << "\n";/*}}}*//*}}}*/
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto &[a, b, c] : fake_edg){
      |               ^
commuter_pass.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [dd, x] = pq.top();
      |              ^
commuter_pass.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for(auto [e, w] : fake_adj[x]){
      |                  ^
commuter_pass.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [e, w] : fake_adj[x]){
      |                  ^
commuter_pass.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for(auto [a, b, c] : fake_edg){
      |              ^
commuter_pass.cpp:99:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         auto [dd, x] = pq.top();
      |              ^
commuter_pass.cpp:103:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         for(auto [e, w] : adj[x]){
      |                  ^
commuter_pass.cpp:113:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |     for(auto [a, b, c] : fake_edg){/*{{{*/
      |              ^
commuter_pass.cpp:136:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |         auto [dd, x] = pq.top();
      |              ^
commuter_pass.cpp:140:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |         for(auto [e, w] : adj[x]){
      |                  ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 329 ms 38832 KB Output is correct
2 Correct 465 ms 41396 KB Output is correct
3 Correct 519 ms 45656 KB Output is correct
4 Correct 407 ms 41952 KB Output is correct
5 Correct 551 ms 45624 KB Output is correct
6 Correct 336 ms 41972 KB Output is correct
7 Correct 550 ms 45456 KB Output is correct
8 Correct 530 ms 45016 KB Output is correct
9 Correct 351 ms 42132 KB Output is correct
10 Correct 325 ms 41996 KB Output is correct
11 Correct 243 ms 29188 KB Output is correct
12 Correct 347 ms 42028 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 41580 KB Output is correct
2 Correct 463 ms 40520 KB Output is correct
3 Correct 499 ms 41184 KB Output is correct
4 Correct 460 ms 40472 KB Output is correct
5 Correct 480 ms 40860 KB Output is correct
6 Correct 530 ms 42156 KB Output is correct
7 Correct 539 ms 43656 KB Output is correct
8 Correct 470 ms 40460 KB Output is correct
9 Correct 495 ms 40972 KB Output is correct
10 Correct 470 ms 40360 KB Output is correct
11 Correct 263 ms 28836 KB Output is correct
12 Correct 513 ms 42504 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 4436 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 18 ms 7612 KB Output is correct
5 Correct 12 ms 3900 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Incorrect 2 ms 724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 329 ms 38832 KB Output is correct
2 Correct 465 ms 41396 KB Output is correct
3 Correct 519 ms 45656 KB Output is correct
4 Correct 407 ms 41952 KB Output is correct
5 Correct 551 ms 45624 KB Output is correct
6 Correct 336 ms 41972 KB Output is correct
7 Correct 550 ms 45456 KB Output is correct
8 Correct 530 ms 45016 KB Output is correct
9 Correct 351 ms 42132 KB Output is correct
10 Correct 325 ms 41996 KB Output is correct
11 Correct 243 ms 29188 KB Output is correct
12 Correct 347 ms 42028 KB Output is correct
13 Correct 478 ms 41580 KB Output is correct
14 Correct 463 ms 40520 KB Output is correct
15 Correct 499 ms 41184 KB Output is correct
16 Correct 460 ms 40472 KB Output is correct
17 Correct 480 ms 40860 KB Output is correct
18 Correct 530 ms 42156 KB Output is correct
19 Correct 539 ms 43656 KB Output is correct
20 Correct 470 ms 40460 KB Output is correct
21 Correct 495 ms 40972 KB Output is correct
22 Correct 470 ms 40360 KB Output is correct
23 Correct 263 ms 28836 KB Output is correct
24 Correct 513 ms 42504 KB Output is correct
25 Correct 17 ms 4436 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 18 ms 7612 KB Output is correct
29 Correct 12 ms 3900 KB Output is correct
30 Correct 1 ms 464 KB Output is correct
31 Incorrect 2 ms 724 KB Output isn't correct
32 Halted 0 ms 0 KB -