Submission #1353822


Source Code Expand

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdio;

alias Tuple!(int, "to", int, "dist") Edge;
alias Tuple!(int, "x", int, "f") Fare;
immutable int INF = 2 * 10^^9 + 1;

void dijkstra(int s, Edge[][] edges, ref int[] dist) {
    dist[s] = 0;
    auto pq = new BinaryHeap!(Array!Edge, "a.dist > b.dist")();
    pq.insert(Edge(s, 0));

    while (!pq.empty) {
        auto e = pq.front;
        pq.popFront;
        if (e.dist > dist[e.to]) continue;
        dist[e.to] = e.dist;
        foreach (f; edges[e.to]) {
            auto new_dist = e.dist + f.dist;
            if (new_dist >= dist[f.to]) continue;
            dist[f.to] = new_dist;
            pq.insert(Edge(f.to, new_dist));
        }
    }

}

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    s = readln.split.map!(to!int);
    auto S = s[0];
    auto G = s[1];
    auto edges = new Edge[][](N);
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        edges[s[0]] ~= Edge(s[1], s[2]);
        edges[s[1]] ~= Edge(s[0], s[2]);
    }
    auto XF = new Fare[](K);
    foreach (i; 0..K) {
        s = readln.split.map!(to!int);
        XF[i] = Fare(s[0], s[1]);
    }

    auto D1 = new int[](N);
    auto D2 = new int[](N);
    fill(D1, INF);
    fill(D2, INF);
    dijkstra(S, edges, D1);
    dijkstra(G, edges, D2);


    int cost(int d) {
        int ret = 0;
        foreach (i; 0..K) {
            if (d < XF[i].x) return ret;
            ret = XF[i].f;
        }
        return ret;
    }


    int ans = INF;
    foreach (i; 0..N) {
        ans = min(ans, cost(D1[i]) + cost(D2[i]));
    }

    ans.writeln;
}

Submission Info

Submission Time
Task D - 切符分割
User nebukuro09
Language D (LDC 0.17.0)
Score 140
Code Size 1877 Byte
Status AC
Exec Time 98 ms
Memory 12028 KB

Judge Result

Set Name direct small large
Score / Max Score 20 / 20 20 / 20 100 / 100
Status
AC × 5
AC × 20
AC × 7
Set Name Test Cases
direct direct/basic_case00, direct/basic_case01, direct/basic_case02, direct/basic_case03, direct/basic_case04
small small/append00, small/append01, small/append02, small/append03, small/append20, small/append21, small/append30, small/basic_case00, small/basic_case01, small/basic_case02, small/basic_case03, small/basic_case04, small/basic_case05, small/basic_case06, small/basic_case07, small/basic_case08, small/basic_case09, small/sample02, small/sample03, small/split00
large large/append10, large/append11, large/append12, large/large_case00, large/large_case01, large/large_case02, large/large_case03
Case Name Status Exec Time Memory
sample00 AC 1 ms 256 KB
sample01 AC 1 ms 256 KB
direct/basic_case00 AC 1 ms 256 KB
direct/basic_case01 AC 1 ms 336 KB
direct/basic_case02 AC 1 ms 380 KB
direct/basic_case03 AC 1 ms 256 KB
direct/basic_case04 AC 1 ms 256 KB
large/append10 AC 83 ms 9468 KB
large/append11 AC 83 ms 9468 KB
large/append12 AC 84 ms 11388 KB
large/large_case00 AC 98 ms 12028 KB
large/large_case01 AC 84 ms 9084 KB
large/large_case02 AC 90 ms 9468 KB
large/large_case03 AC 96 ms 10108 KB
small/append00 AC 1 ms 256 KB
small/append01 AC 1 ms 256 KB
small/append02 AC 1 ms 256 KB
small/append03 AC 1 ms 256 KB
small/append20 AC 1 ms 380 KB
small/append21 AC 1 ms 380 KB
small/append30 AC 1 ms 256 KB
small/basic_case00 AC 1 ms 256 KB
small/basic_case01 AC 1 ms 256 KB
small/basic_case02 AC 1 ms 380 KB
small/basic_case03 AC 1 ms 256 KB
small/basic_case04 AC 1 ms 256 KB
small/basic_case05 AC 1 ms 256 KB
small/basic_case06 AC 1 ms 336 KB
small/basic_case07 AC 1 ms 256 KB
small/basic_case08 AC 1 ms 256 KB
small/basic_case09 AC 1 ms 380 KB
small/sample02 AC 1 ms 256 KB
small/sample03 AC 1 ms 256 KB
small/split00 AC 1 ms 256 KB