Submission #2807493


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

struct Edge {
    int to;
    lli cost;
    Edge(int t, lli c) {
        to = t;
        cost = c;
    }
    Edge() {}
    bool operator<(const Edge e) const {
        return cost > e.cost;
    }
};

const lli inf = 1LL << 60;

void dijk(vector<vector<Edge>> &G, vector<lli> &minCost, int srt, int node) {
    vector<bool> used(node, false);
    minCost.assign(node, inf);
    priority_queue<Edge, vector<Edge>> pq;
    pq.emplace(srt, 0);
    minCost[srt] = 0;
    while (pq.size()) {
        auto elem = pq.top();
        pq.pop();
        if (used[elem.to]) continue;
        used[elem.to] = true;
        for (auto nxt : G[elem.to]) {
            lli c = elem.cost + nxt.cost;
            if (c < minCost[nxt.to]) {
                minCost[nxt.to] = c;
                pq.emplace(nxt.to, c);
            }
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--;
    t--;
    vector<vector<Edge>> enG(n), snG(n);
    REP(i, 0, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        enG[u].push_back(Edge(v, a));
        enG[v].push_back(Edge(u, a));
        snG[u].push_back(Edge(v, b));
        snG[v].push_back(Edge(u, b));
    }
    vector<lli> enC(n), snC(n);
    dijk(enG, enC, s, n);
    dijk(snG, snC, t, n);
    vector<lli> minCost(n, inf);
    REP(i, 0, n) {
        minCost[i] = enC[i] + snC[i];
    }
    for (int i = n - 2; i >= 0; i--) {
        minCost[i] = min(minCost[i], minCost[i + 1]);
    }
    REP(i, 0, n) {
        cout << 1'000'000'000'000'000LL - minCost[i] << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Saving Snuuk
User commy
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2175 Byte
Status
Exec Time 400 ms
Memory 19012 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sampleRnd.txt, sampleT.txt
All 400 / 400 00yorimichi.txt, 11_0.txt, 11_1.txt, 11_2.txt, 11_3.txt, 11_4.txt, 1n1m1.txt, 1oo_0.txt, 1oo_1.txt, 1oo_2.txt, 1oo_3.txt, 1oo_4.txt, dangou_0.txt, dangou_1.txt, dangou_2.txt, dangou_3.txt, dangou_4.txt, edge.txt, high_0.txt, high_1.txt, high_2.txt, high_3.txt, high_4.txt, low_0.txt, low_1.txt, low_2.txt, low_3.txt, low_4.txt, oo1_0.txt, oo1_1.txt, oo1_2.txt, oo1_3.txt, oo1_4.txt, path_0.txt, path_1.txt, path_2.txt, path_3.txt, path_4.txt, path_5.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sampleRnd.txt, sampleT.txt, slast_0.txt, slast_1.txt, slast_2.txt, slast_3.txt, slast_4.txt, tlast_0.txt, tlast_1.txt, tlast_2.txt, tlast_3.txt, tlast_4.txt
Case Name Status Exec Time Memory
00yorimichi.txt 324 ms 18176 KB
11_0.txt 309 ms 15588 KB
11_1.txt 169 ms 11520 KB
11_2.txt 219 ms 11820 KB
11_3.txt 392 ms 18980 KB
11_4.txt 349 ms 16880 KB
1n1m1.txt 264 ms 13384 KB
1oo_0.txt 266 ms 15084 KB
1oo_1.txt 280 ms 15588 KB
1oo_2.txt 112 ms 8576 KB
1oo_3.txt 296 ms 16224 KB
1oo_4.txt 288 ms 15584 KB
dangou_0.txt 123 ms 11264 KB
dangou_1.txt 215 ms 11824 KB
dangou_2.txt 330 ms 15568 KB
dangou_3.txt 89 ms 6272 KB
dangou_4.txt 397 ms 18940 KB
edge.txt 364 ms 18944 KB
high_0.txt 119 ms 7432 KB
high_1.txt 150 ms 9728 KB
high_2.txt 363 ms 17968 KB
high_3.txt 19 ms 1664 KB
high_4.txt 274 ms 13888 KB
low_0.txt 99 ms 11008 KB
low_1.txt 104 ms 9264 KB
low_2.txt 275 ms 16464 KB
low_3.txt 249 ms 15048 KB
low_4.txt 175 ms 11604 KB
oo1_0.txt 307 ms 17008 KB
oo1_1.txt 246 ms 14340 KB
oo1_2.txt 215 ms 12664 KB
oo1_3.txt 153 ms 11264 KB
oo1_4.txt 201 ms 12432 KB
path_0.txt 320 ms 16128 KB
path_1.txt 314 ms 16128 KB
path_2.txt 147 ms 8064 KB
path_3.txt 189 ms 9984 KB
path_4.txt 100 ms 5632 KB
path_5.txt 286 ms 14208 KB
rnd_0.txt 315 ms 15416 KB
rnd_1.txt 366 ms 18272 KB
rnd_2.txt 39 ms 2304 KB
rnd_3.txt 354 ms 17340 KB
rnd_4.txt 224 ms 12396 KB
sampleRnd.txt 1 ms 256 KB
sampleT.txt 1 ms 256 KB
slast_0.txt 303 ms 15152 KB
slast_1.txt 139 ms 8192 KB
slast_2.txt 363 ms 17920 KB
slast_3.txt 236 ms 12880 KB
slast_4.txt 319 ms 16092 KB
tlast_0.txt 160 ms 10496 KB
tlast_1.txt 282 ms 14476 KB
tlast_2.txt 351 ms 17488 KB
tlast_3.txt 388 ms 19008 KB
tlast_4.txt 400 ms 19012 KB