1851: 迪杰斯特拉算法
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：11
题目描述
任意给出一带权有向图 G 和源点 v，求从 v 到 G 中其余各顶点的最短路径。
输入
输入的第一行包括三个整数，M, N, Q用空格隔开，分别表示有向图G的顶点的个数，有向图的边数及源点 v。（2 ≤ M ≤ 10,0 ≤ N ≤ 90，1 ≤ Q ≤ M）其余各行依次输入边的始点，终点和边上的权值S(1 ≤ S ≤ 10000），假设该图中不存在环，各顶点到自己的距离为 0。
输出
输出包括一行，依次输出该顶点到各顶点的最短路径长度，并以空格隔开，如不能到达则输出 -1。
样例输入 复制
6 8 1
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60样例输出 复制
0 -1 10 50 30 60