Submission #3141758

Source Code Expand

Copy
```import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;
import std.array;
import std.math;

void stringsTo(string, T...)(string str, ref T t) {
auto s = str.split();
assert(s.length == t.length);
foreach(ref ti; t) {
ti = s[0].to!(typeof(ti));
s = s[1..\$];
}
}

long INF = pow(10, 9);

struct Node {
int   u; // :u ノードのインデックス
ulong k; // :k u の出次数
int[] v; // :v u に隣接する頂点の番号
int[int] w; // :w 隣接する頂点への重み
};

class Graph {
public int n;
public Node[] nodes;
public long[][] dist;

this(int n) {
this.n = n;
this.nodes = new Node[n];
foreach (int i, ref node; this.nodes) {
node.u = i;
}
this.dist = new long [][](n,n);
}

void addGraphEdge(int u, int v, int w) {
this.nodes[u].v ~= v;
this.nodes[u].w[v] = w;
this.nodes[u].k = this.nodes[u].v.length;
}

void warshallFloyd() {
for (int i = 0; i < this.nodes.length; i++ ) {
for (int j = 0; j < this.nodes.length; j++ ) {
int* val = j in this.nodes[i].w;
if (val != null) {
this.dist[i][j] = *val;
} else {
this.dist[i][j] = INF;
}
}
this.dist[i][i] = 0;
}

for (int k = 0; k < this.nodes.length; k++) {
for (int i = 0; i < this.nodes.length; i++) {
for (int j = 0; j < this.nodes.length; j++) {
if (this.dist[i][k] != INF && this.dist[k][j] != INF) {
this.dist[i][j] = min(this.dist[i][j], this.dist[i][k] + this.dist[k][j]);
}
}
}
}
}
}

void main()
{

string lines;
string buf;

while (!stdin.eof) {
lines ~= buf;
}

string[] array = splitLines(lines);

int H,W;
stringsTo(array[0], H, W);
Graph graph = new Graph(10);

foreach ( int i, str; array[1..10+1]) {
foreach ( int j, int w; str.split(" ").map!(s => s.to!int).array ) {
}
}

graph.warshallFloyd();

int ans = 0;

foreach ( str; array[11..12+H-1] ) {
//writeln(str);
foreach ( int a; str.split(" ").map!(s => s.to!int).array ) {
if (a != 1 && a != -1) {
ans += graph.dist[a][1];
//writeln(graph.dist[a][1]);
}
}
}

writeln(ans);
}
```

#### Submission Info

Submission Time 2018-09-06 12:16:13+0900 D - Wall hiroyuking D (DMD64 v2.070.1) 400 2336 Byte AC 6 ms 4092 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
01.txt 6 ms 3964 KB
02.txt 5 ms 2044 KB
03.txt 5 ms 2044 KB
04.txt 5 ms 2044 KB
05.txt 4 ms 1532 KB
06.txt 5 ms 2044 KB
07.txt 5 ms 2044 KB
08.txt 2 ms 508 KB
09.txt 2 ms 636 KB
10.txt 5 ms 2044 KB
11.txt 5 ms 2044 KB
12.txt 6 ms 3580 KB
13.txt 6 ms 3964 KB
14.txt 6 ms 4092 KB
15.txt 1 ms 256 KB
16.txt 5 ms 2044 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB