oj.uz

답안 #453557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
453557 2021-08-04T12:21:16 Z Karliver Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 818 ms 31508 KB 
    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<ll, ll> pairs;

const ll INF = 2e18;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}


vector<pair<ll, ll>> graph[100001];
ll du[100001], dv[100001], ds[100001], dp[2][100001], ans;
bool visited[100001];

void dijkstra1(ll start, ll arr[]) {
    fill(visited, visited + 100001, false);

    priority_queue<pair<ll, ll>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        ll c, node;
        tie(c, node) = pq.top();
        pq.pop();

        if (!visited[node]) {
            arr[node] = -c;
            visited[node] = true;
            for (auto& i : graph[node]) pq.push({c - i.second, i.first});
        }
    }
}

void dijkstra2(ll start, ll end) {
    fill(dp[0], dp[0] + 100001, LLONG_MAX / 2);
    fill(dp[1], dp[1] + 100001, LLONG_MAX / 2);
    fill(visited, visited + 100001, false);

    priority_queue<pair<ll, pair<ll, ll>>> pq;
    pq.push({0, {start, 0}});
    dp[0][0] = dp[1][0] = LLONG_MAX/ 2;
    while (!pq.empty()) {
        ll c, node, par;
        pair<ll, ll> p;
        tie(c, p) = pq.top();
        tie(node, par) = p;
        pq.pop();

        if (!visited[node]) {
            visited[node] = true;
            ds[node] = -c;
            dp[0][node] = min(du[node], dp[0][par]);
            dp[1][node] = min(dv[node], dp[1][par]);
            for (auto i : graph[node]) pq.push({c - i.second, {i.first, node}});
        } else if (-c == ds[node]) {
            if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node]) {
                dp[0][node] = min(du[node], dp[0][par]);
                dp[1][node] = min(dv[node], dp[1][par]);
            }
        }
    }

    ans = min(ans, dp[0][end] + dp[1][end]);
}


void solve() {

    ll n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    dijkstra1(u, du);
    dijkstra1(v, dv);

    ans = du[v];

    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << '\n';

}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 650 ms 27208 KB Output is correct
2 Correct 691 ms 26664 KB Output is correct
3 Correct 645 ms 26396 KB Output is correct
4 Correct 630 ms 26332 KB Output is correct
5 Correct 568 ms 23140 KB Output is correct
6 Correct 696 ms 26988 KB Output is correct
7 Correct 818 ms 26580 KB Output is correct
8 Correct 641 ms 26916 KB Output is correct
9 Correct 700 ms 27104 KB Output is correct
10 Correct 661 ms 31456 KB Output is correct
11 Correct 194 ms 13936 KB Output is correct
12 Correct 685 ms 31508 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 26884 KB Output is correct
2 Correct 544 ms 23124 KB Output is correct
3 Correct 544 ms 26496 KB Output is correct
4 Correct 542 ms 23172 KB Output is correct
5 Correct 527 ms 22808 KB Output is correct
6 Correct 538 ms 26252 KB Output is correct
7 Correct 516 ms 22960 KB Output is correct
8 Correct 565 ms 23108 KB Output is correct
9 Correct 583 ms 23072 KB Output is correct
10 Correct 560 ms 26244 KB Output is correct
11 Correct 180 ms 11844 KB Output is correct
12 Correct 532 ms 26192 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 7124 KB Output is correct
2 Correct 3 ms 4300 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 86 ms 9844 KB Output is correct
5 Correct 44 ms 8044 KB Output is correct
6 Correct 5 ms 4428 KB Output is correct
7 Correct 6 ms 4556 KB Output is correct
8 Correct 8 ms 4676 KB Output is correct
9 Correct 5 ms 4428 KB Output is correct
10 Correct 44 ms 8024 KB Output is correct
11 Correct 3 ms 4300 KB Output is correct
12 Correct 3 ms 4300 KB Output is correct
13 Correct 4 ms 4300 KB Output is correct
14 Correct 4 ms 4480 KB Output is correct
15 Correct 4 ms 4428 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 650 ms 27208 KB Output is correct
2 Correct 691 ms 26664 KB Output is correct
3 Correct 645 ms 26396 KB Output is correct
4 Correct 630 ms 26332 KB Output is correct
5 Correct 568 ms 23140 KB Output is correct
6 Correct 696 ms 26988 KB Output is correct
7 Correct 818 ms 26580 KB Output is correct
8 Correct 641 ms 26916 KB Output is correct
9 Correct 700 ms 27104 KB Output is correct
10 Correct 661 ms 31456 KB Output is correct
11 Correct 194 ms 13936 KB Output is correct
12 Correct 685 ms 31508 KB Output is correct
13 Correct 589 ms 26884 KB Output is correct
14 Correct 544 ms 23124 KB Output is correct
15 Correct 544 ms 26496 KB Output is correct
16 Correct 542 ms 23172 KB Output is correct
17 Correct 527 ms 22808 KB Output is correct
18 Correct 538 ms 26252 KB Output is correct
19 Correct 516 ms 22960 KB Output is correct
20 Correct 565 ms 23108 KB Output is correct
21 Correct 583 ms 23072 KB Output is correct
22 Correct 560 ms 26244 KB Output is correct
23 Correct 180 ms 11844 KB Output is correct
24 Correct 532 ms 26192 KB Output is correct
25 Correct 44 ms 7124 KB Output is correct
26 Correct 3 ms 4300 KB Output is correct
27 Correct 4 ms 4300 KB Output is correct
28 Correct 86 ms 9844 KB Output is correct
29 Correct 44 ms 8044 KB Output is correct
30 Correct 5 ms 4428 KB Output is correct
31 Correct 6 ms 4556 KB Output is correct
32 Correct 8 ms 4676 KB Output is correct
33 Correct 5 ms 4428 KB Output is correct
34 Correct 44 ms 8024 KB Output is correct
35 Correct 3 ms 4300 KB Output is correct
36 Correct 3 ms 4300 KB Output is correct
37 Correct 4 ms 4300 KB Output is correct
38 Correct 4 ms 4480 KB Output is correct
39 Correct 4 ms 4428 KB Output is correct
40 Correct 616 ms 31024 KB Output is correct
41 Correct 632 ms 31252 KB Output is correct
42 Correct 628 ms 31296 KB Output is correct
43 Correct 159 ms 14036 KB Output is correct
44 Correct 160 ms 14028 KB Output is correct
45 Correct 522 ms 25144 KB Output is correct
46 Correct 586 ms 24824 KB Output is correct
47 Correct 618 ms 26684 KB Output is correct
48 Correct 191 ms 13524 KB Output is correct
49 Correct 655 ms 29364 KB Output is correct
50 Correct 578 ms 25180 KB Output is correct
51 Correct 530 ms 25160 KB Output is correct