oj.uz

답안 #535750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535750 2022-03-11T05:57:41 Z sam571128 Robot (JOI21_ho_t4) C++17
34 / 100
 56 ms 45604 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e3 + 5, M = 2e3 + 5;
struct edge {
    int v, c, p;
};

int dp[N][M], from[N][M];
vector<edge> adj[N];
int sum[M];

signed main() {
    fastio
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u].push_back({v, c, p});
        adj[v].push_back({u, c, p});
    }

    fill(&dp[0][0], &dp[N - 1][M - 1], 1e18);

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    dp[1][0] = 0;
    pq.push({0, {1, 0}});
    //dis, vertex, lst

    while (!pq.empty()) {
        auto [ww, pp] = pq.top();
        pq.pop();
        auto [u, lst] = pp;

        if (ww > dp[u][lst])
            continue;

        for (auto [v, c, p] : adj[u]){
            if(v == lst) p = 0;
            sum[c] += p;
        }

        for (auto [v, c, p] : adj[u]) {
            if(v == lst) p = 0;
            //Dont change this edge, change all others
            if (dp[v][0] > dp[u][lst] + min(p,sum[c] - p)) {
                dp[v][0] = dp[u][lst] + min(p,sum[c] - p);
                pq.push({dp[v][0], {v, 0}});
            }

            //Change this edge, using p
            if (dp[v][u] > dp[u][lst] + p) {
                dp[v][u] = dp[u][lst] + p;
                pq.push({dp[v][u], {v, u}});
            }
        }

        for (auto [v, c, p] : adj[u]){
            if(v == lst) p = 0;
            sum[c] -= p;
        }
    }

    int ans = 1e18;

    for (int i = 0; i <= m; i++) {
        ans = min(ans, dp[n][i]);
    }

    cout << (ans == 1e18 ? -1 : ans) << "\n";
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16064 KB Output is correct
3 Correct 8 ms 16084 KB Output is correct
4 Correct 7 ms 16084 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 8 ms 16176 KB Output is correct
9 Correct 37 ms 16360 KB Output is correct
10 Correct 24 ms 16468 KB Output is correct
11 Correct 36 ms 16388 KB Output is correct
12 Correct 19 ms 16304 KB Output is correct
13 Correct 47 ms 16456 KB Output is correct
14 Correct 44 ms 16444 KB Output is correct
15 Correct 8 ms 16212 KB Output is correct
16 Correct 9 ms 16244 KB Output is correct
17 Correct 8 ms 16284 KB Output is correct
18 Correct 8 ms 16160 KB Output is correct
19 Correct 10 ms 16468 KB Output is correct
20 Correct 10 ms 16248 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 56 ms 45604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16064 KB Output is correct
3 Correct 8 ms 16084 KB Output is correct
4 Correct 7 ms 16084 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 8 ms 16176 KB Output is correct
9 Correct 37 ms 16360 KB Output is correct
10 Correct 24 ms 16468 KB Output is correct
11 Correct 36 ms 16388 KB Output is correct
12 Correct 19 ms 16304 KB Output is correct
13 Correct 47 ms 16456 KB Output is correct
14 Correct 44 ms 16444 KB Output is correct
15 Correct 8 ms 16212 KB Output is correct
16 Correct 9 ms 16244 KB Output is correct
17 Correct 8 ms 16284 KB Output is correct
18 Correct 8 ms 16160 KB Output is correct
19 Correct 10 ms 16468 KB Output is correct
20 Correct 10 ms 16248 KB Output is correct
21 Runtime error 56 ms 45604 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -