多源最短路 1235

Time Limit: 1 Sec Memory Limit: 128 MB

Submission：25 AC：5 Score：100

给出一个有向图，请输出从某些点出发到所有点的最短路径长度。

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的数量。

接下来一行有S个整数，表示出发点的编号

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度(长度不会超过100)。

一行，包含N个用空格分隔的整数，其中第i个整数表示从任一出发点出发到点i的最短路径长度（若i为出发点则最短路径长度为0，若从点S无法到达点i，则最短路径长度为-1）

input:

4 6 1 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4

output:

0 2 4 3

N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000