oj.uz

Submission #810943

# Submission time Handle Problem Language Result Execution time Memory
810943 2023-08-06T17:51:21 Z winthemcut3 Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 188 ms 23964 KB 
#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 1e5 + 5;
struct edge {
    int des; ll c;
};
struct cmp {
    bool operator() (const edge &t1, const edge &t2) {
        return t1.c > t2.c;
    }
};
int n, m, S, T, U, V;
vector<ll> ds, dd[2];
ll dp[2][mxN];
vector<edge> g[mxN];
void dijkstra(int s, vector<ll> &d) {
    d.resize(n+7, 1e18);
    priority_queue<edge, vector<edge>, cmp> q;
    q.push({s, 0}); d[s] = 0;
    while(q.size()) {
        int u = q.top().des;
        ll du = q.top().c;
        q.pop();
        if(du != d[u]) continue;
        for(edge &v_ : g[u]) {
            int v = v_.des; ll c = v_.c;
            if(d[v] > d[u] + c) {
                d[v] = d[u] + c;
                q.push({v, d[v]});
            }
        }
    }
}
ll res;
bool vis[mxN];
void dfs(int u)
{
    if (vis[u]) return;
    vis[u]=1;
    dp[0][u]=dd[0][u];
    dp[1][u]=dd[1][u];
    for (auto [nl, nw]:g[u])
    {
        if (ds[nl]+nw==ds[u])
        {
            dfs(nl);
            dp[0][u]=min(dp[0][u], dp[0][nl]);
            dp[1][u]=min(dp[1][u], dp[1][nl]);
        }
    }
    res=min({res, dp[0][u]+dd[1][u], dp[1][u]+dd[0][u]});
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> m >> S >> T >> U >> V;
    FOR(i, 1, m) {
        int u, v, c; cin >> u >> v >> c;
        g[u].PB({v, c}); g[v].PB({u, c});
    }
    dijkstra(S, ds);
    dijkstra(U, dd[0]);
    dijkstra(V, dd[1]);

    res = dd[0][V];
    memset(dp, 0x3f, sizeof dp);
    dfs(T);

    cout << res;
    return 0;
}

/*

*/

Compilation message

commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for (auto [nl, nw]:g[u])
      |               ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 18548 KB Output is correct
2 Correct 162 ms 17288 KB Output is correct
3 Correct 158 ms 22240 KB Output is correct
4 Correct 135 ms 18396 KB Output is correct
5 Correct 149 ms 17192 KB Output is correct
6 Correct 150 ms 18620 KB Output is correct
7 Correct 156 ms 17272 KB Output is correct
8 Correct 154 ms 17400 KB Output is correct
9 Correct 147 ms 17148 KB Output is correct
10 Correct 120 ms 21492 KB Output is correct
11 Correct 59 ms 17184 KB Output is correct
12 Correct 150 ms 21484 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 19324 KB Output is correct
2 Correct 177 ms 19780 KB Output is correct
3 Correct 170 ms 19156 KB Output is correct
4 Correct 162 ms 19620 KB Output is correct
5 Correct 170 ms 20068 KB Output is correct
6 Correct 161 ms 21796 KB Output is correct
7 Correct 188 ms 22376 KB Output is correct
8 Correct 164 ms 19612 KB Output is correct
9 Correct 178 ms 20312 KB Output is correct
10 Correct 165 ms 19252 KB Output is correct
11 Correct 60 ms 16824 KB Output is correct
12 Correct 171 ms 23964 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5588 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 11 ms 7640 KB Output is correct
5 Correct 7 ms 5960 KB Output is correct
6 Correct 2 ms 4352 KB Output is correct
7 Correct 3 ms 4360 KB Output is correct
8 Correct 3 ms 4484 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 7 ms 5972 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct
14 Correct 3 ms 4224 KB Output is correct
15 Correct 2 ms 4232 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 18548 KB Output is correct
2 Correct 162 ms 17288 KB Output is correct
3 Correct 158 ms 22240 KB Output is correct
4 Correct 135 ms 18396 KB Output is correct
5 Correct 149 ms 17192 KB Output is correct
6 Correct 150 ms 18620 KB Output is correct
7 Correct 156 ms 17272 KB Output is correct
8 Correct 154 ms 17400 KB Output is correct
9 Correct 147 ms 17148 KB Output is correct
10 Correct 120 ms 21492 KB Output is correct
11 Correct 59 ms 17184 KB Output is correct
12 Correct 150 ms 21484 KB Output is correct
13 Correct 163 ms 19324 KB Output is correct
14 Correct 177 ms 19780 KB Output is correct
15 Correct 170 ms 19156 KB Output is correct
16 Correct 162 ms 19620 KB Output is correct
17 Correct 170 ms 20068 KB Output is correct
18 Correct 161 ms 21796 KB Output is correct
19 Correct 188 ms 22376 KB Output is correct
20 Correct 164 ms 19612 KB Output is correct
21 Correct 178 ms 20312 KB Output is correct
22 Correct 165 ms 19252 KB Output is correct
23 Correct 60 ms 16824 KB Output is correct
24 Correct 171 ms 23964 KB Output is correct
25 Correct 9 ms 5588 KB Output is correct
26 Correct 2 ms 4180 KB Output is correct
27 Correct 2 ms 4180 KB Output is correct
28 Correct 11 ms 7640 KB Output is correct
29 Correct 7 ms 5960 KB Output is correct
30 Correct 2 ms 4352 KB Output is correct
31 Correct 3 ms 4360 KB Output is correct
32 Correct 3 ms 4484 KB Output is correct
33 Correct 2 ms 4308 KB Output is correct
34 Correct 7 ms 5972 KB Output is correct
35 Correct 2 ms 4180 KB Output is correct
36 Correct 2 ms 4180 KB Output is correct
37 Correct 2 ms 4180 KB Output is correct
38 Correct 3 ms 4224 KB Output is correct
39 Correct 2 ms 4232 KB Output is correct
40 Correct 136 ms 22280 KB Output is correct
41 Correct 173 ms 21632 KB Output is correct
42 Correct 148 ms 21532 KB Output is correct
43 Correct 76 ms 17916 KB Output is correct
44 Correct 102 ms 17864 KB Output is correct
45 Correct 150 ms 21428 KB Output is correct
46 Correct 143 ms 20416 KB Output is correct
47 Correct 139 ms 22188 KB Output is correct
48 Correct 64 ms 14892 KB Output is correct
49 Correct 124 ms 21916 KB Output is correct
50 Correct 161 ms 20788 KB Output is correct
51 Correct 141 ms 20620 KB Output is correct