CHD-ACM CHDOJ 首页 题库 题单 比赛 评测 用户 讨论 帮助
工具
云剪贴板 树图画板 代码对比
登录 注册

2244: 【入门】最短路径

时间限制：1000 ms 内存限制：32 MB
上传者：
提交：73 通过：37
提交提交记录讨论统计

题目描述

在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。

输入格式

输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。（2≤s<n≤50）
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值（0≤权值≤100）；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

输出格式

只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。
请注意行尾输出换行。

输入样例 复制 

4 2
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

输出样例 复制 

6 4 7

数据范围与提示

分类标签