oj.uz

Submission #241337

# Submission time Handle Problem Language Result Execution time Memory
241337 2020-06-24T04:13:53 Z thecodingwizard Ceste (COCI17_ceste) C++11
96 / 160
 103 ms 1408 KB 
#include <bits/stdc++.h>

using namespace std;

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;
    int best[2000]; for (int i = 0; i < n; i++) best[i] = 1e9+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], 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] == 1e9+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 6 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 20 ms 1408 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 1404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 1404 KB Output isn't correct
2 Halted 0 ms 0 KB -