Submission #241337

#	Time	Username	Problem	Language	Result	Execution time	Memory
241337		thecodingwizard	Ceste (COCI17_ceste)	C++11	96 / 160	103 ms	1408 KiB

ceste

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16