oj.uz

Submission #485311

# Submission time Handle Problem Language Result Execution time Memory
485311 2021-11-07T05:16:01 Z PurpleCrayon Robot (JOI21_ho_t4) C++17
0 / 100
 427 ms 38276 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

int n, m;
vector<ar<int, 3>> input[MAXN];
vector<ar<int, 2>> adj[MAXN];
map<int, ll> sum[MAXN];
ll dist[MAXN];

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c, p; cin >> a >> b >> c >> p, --a, --b, --c;
        input[a].push_back({b, c, p}), input[b].push_back({a, c, p});
        sum[a][c] += p, sum[b][c] += p;
    }
    for (int a = 0; a < n; a++) {
        for (auto [b, c, p] : input[a]) {
            int cost = min((long long) p, sum[a][c] - p);

            adj[a].push_back({b, cost});
        }
        dist[a] = INF;
    }

    min_pq<pair<ll, int>> q; q.push({0, 0});
    dist[0] = 0;

    while (sz(q)) {
        auto [d, c] = q.top(); q.pop();
        if (d != dist[c]) continue;

        for (auto [nxt, w] : adj[c]) if (dist[nxt] > dist[c] + w) {
            dist[nxt] = dist[c] + w;
            q.push({dist[nxt], nxt});
        }
    }
    ll ans = dist[n-1];
    if (ans == INF) ans = -1;
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9712 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Incorrect 6 ms 9924 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19564 KB Output is correct
2 Correct 34 ms 14760 KB Output is correct
3 Correct 88 ms 21104 KB Output is correct
4 Correct 53 ms 16464 KB Output is correct
5 Incorrect 427 ms 38276 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9712 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Incorrect 6 ms 9924 KB Output isn't correct
10 Halted 0 ms 0 KB -