oj.uz

답안 #865476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865476 2023-10-24T09:01:35 Z Asamai Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 260 ms 21280 KB 
#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 1e5 + 5;
const ll inf = 1e18;

int n, m, S, T, U, V;
vector<pii> adj[MAX_N];
int distU[MAX_N], distV[MAX_N], distS[MAX_N], back[MAX_N];
int dp[MAX_N][2];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int ans = inf;

void dijkstra1(int start, int *dist) {
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;
            if (currW + w < dist[v]) {
                dist[v] = currW + w;
                pq.push({dist[v], v});
            }
        }
    }
}

void sol(int start, int end) {
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = distS[i] = inf;
    }
    distS[start] = 0;
    dp[start][0] = distU[start];
    dp[start][1] = distV[start];

    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        if (currW > distS[u]) {
            continue;
        }

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;

            if (currW + w > distS[v]) {
                continue;
            }

            if (currW + w == distS[v]) {
                if (dp[v][0] + dp[u][0] > dp[u][0] + dp[u][1]) {
                    dp[v][0] = dp[u][0];
                    dp[v][1] = dp[u][1];
                }
            }
            else {
                distS[v] = currW + w;
                pq.push({distS[v], v});
                dp[v][0] = min(dp[u][0], distU[v]);
                dp[v][1] = min(dp[u][1], distV[v]);
            }
        }
    }

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    dijkstra1(U, distU);
    dijkstra1(V, distV);

    ans = distU[V];

    sol(S, T);
    sol(T, S);

    cout << ans;

    return 0;
}

/*


Tuesday, 24 October 2023
15:16:46
*/

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 18880 KB Output is correct
2 Correct 211 ms 18796 KB Output is correct
3 Correct 195 ms 19936 KB Output is correct
4 Correct 200 ms 18888 KB Output is correct
5 Correct 192 ms 18760 KB Output is correct
6 Correct 230 ms 21280 KB Output is correct
7 Correct 211 ms 20924 KB Output is correct
8 Correct 210 ms 20800 KB Output is correct
9 Correct 197 ms 20928 KB Output is correct
10 Correct 144 ms 20952 KB Output is correct
11 Correct 112 ms 13904 KB Output is correct
12 Correct 260 ms 20936 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 18884 KB Output is correct
2 Correct 202 ms 18756 KB Output is correct
3 Correct 229 ms 18644 KB Output is correct
4 Correct 194 ms 18732 KB Output is correct
5 Correct 209 ms 18760 KB Output is correct
6 Correct 188 ms 18788 KB Output is correct
7 Correct 198 ms 18628 KB Output is correct
8 Correct 196 ms 18772 KB Output is correct
9 Correct 217 ms 18888 KB Output is correct
10 Correct 196 ms 18880 KB Output is correct
11 Correct 52 ms 12624 KB Output is correct
12 Correct 191 ms 18884 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 18880 KB Output is correct
2 Correct 211 ms 18796 KB Output is correct
3 Correct 195 ms 19936 KB Output is correct
4 Correct 200 ms 18888 KB Output is correct
5 Correct 192 ms 18760 KB Output is correct
6 Correct 230 ms 21280 KB Output is correct
7 Correct 211 ms 20924 KB Output is correct
8 Correct 210 ms 20800 KB Output is correct
9 Correct 197 ms 20928 KB Output is correct
10 Correct 144 ms 20952 KB Output is correct
11 Correct 112 ms 13904 KB Output is correct
12 Correct 260 ms 20936 KB Output is correct
13 Correct 219 ms 18884 KB Output is correct
14 Correct 202 ms 18756 KB Output is correct
15 Correct 229 ms 18644 KB Output is correct
16 Correct 194 ms 18732 KB Output is correct
17 Correct 209 ms 18760 KB Output is correct
18 Correct 188 ms 18788 KB Output is correct
19 Correct 198 ms 18628 KB Output is correct
20 Correct 196 ms 18772 KB Output is correct
21 Correct 217 ms 18888 KB Output is correct
22 Correct 196 ms 18880 KB Output is correct
23 Correct 52 ms 12624 KB Output is correct
24 Correct 191 ms 18884 KB Output is correct
25 Incorrect 6 ms 6488 KB Output isn't correct
26 Halted 0 ms 0 KB -