oj.uz

Submission #241338

# Submission time Handle Problem Language Result Execution time Memory
241338 2020-06-24T04:14:58 Z thecodingwizard Ceste (COCI17_ceste) C++11
160 / 160
 127 ms 3700 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

struct edge {
    int to, time, cost;
};

struct state {
    int id, cost, time;
    bool operator<(const state &other) const {
        return cost == other.cost ? time > other.time : cost > other.cost;
    }
};

int main() {
    int n, m; cin >> n >> m;
    vector<edge> adj[2000];
    for (int i = 0; i < m; i++) {
        int a, b, t, c; cin >> a >> b >> t >> c;
        --a; --b;
        adj[a].push_back({b,t,c});
        adj[b].push_back({a,t,c});
    }

    int minTime[2000]; for (int i = 0; i < n; i++) minTime[i] = 1e9+10;
    ll best[2000]; for (int i = 0; i < n; i++) best[i] = 9e18+10;
    int mx = 2000*2000;

    minTime[0] = best[0] = 0;
    priority_queue<state> pq;
    pq.push({0,0,0});
    while (!pq.empty()) {
        state u = pq.top(); pq.pop();
        if (u.time > minTime[u.id]) continue;
        minTime[u.id] = u.time;
        best[u.id] = min(best[u.id], (ll)u.time*u.cost);
        for (edge v : adj[u.id]) {
            if (u.time + v.time <= mx && u.time + v.time < minTime[v.to]) {
                pq.push({v.to,u.cost+v.cost,u.time+v.time});
            }
        }
    }

    for (int i = 1; i < n; i++) {
        if (best[i] == 9e18+10) cout << -1 << endl;
        else cout << best[i] << endl;
    }

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 704 KB Output is correct
2 Correct 19 ms 960 KB Output is correct
3 Correct 21 ms 1408 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 1396 KB Output is correct
2 Correct 126 ms 3700 KB Output is correct
3 Correct 10 ms 768 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 768 KB Output is correct
2 Correct 127 ms 3692 KB Output is correct
3 Correct 13 ms 512 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 760 KB Output is correct
2 Correct 110 ms 1404 KB Output is correct
3 Correct 100 ms 1404 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1396 KB Output is correct
2 Correct 95 ms 1396 KB Output is correct
3 Correct 127 ms 1520 KB Output is correct