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 |
|
|
|
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 |