1493: 【秋季】CSP完善程序(求最短距离)
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：25
Solved：5
Description
求最短距离
给定一个有n个顶点m条边的有向图，请计算从顶点1(first=1)出发到各点的最短距离。
输入： 第一行包含二个数nm，分别表示顶点数n，有向边个数m。
接下来m行包含三个数uvw，表示一条从u到v，长度为w的边。
输出：n个数，分别为起点到该点的最短距离。
算法说明：
1.用dist数组记录点到有向图的任意一点距离，初始化起点(first)距离为0，其余点均为MAX (0x3f)，起点入队。
2.判断该点是否存在。（未存在就入队，标记）
3.队首出队，并将该点标记为没有访问过，方便下次入队。
4.遍历以队首为起点的有向边 如果存在更短的距离则更新dist[i]。
5.如果i不在队列中，则入队标记，一直到循环为空。
供选择的答案:
(1) A. q.push(i) B. q.front() C. q.pop() D. q.push(first）
(2) A. to[i] B. dist[first] C. w[i] D. dist[i]
(3) A. dist[j]=dist[now]+w[now]; B. dist[j]= abs(dist[i]+w[now] )
C. dist[j]=dist[now]+w[i] D. dist[j]=dist[i]+w[j]
(4) A. q.push(j) B. q.front() C. q.push(i) D. q.pop(）
(5) A. add() B. spfa(1) C. add(abc) D. spfa()
给定一个有n个顶点m条边的有向图，请计算从顶点1(first=1)出发到各点的最短距离。
输入： 第一行包含二个数nm，分别表示顶点数n，有向边个数m。
接下来m行包含三个数uvw，表示一条从u到v，长度为w的边。
输出：n个数，分别为起点到该点的最短距离。
算法说明：
1.用dist数组记录点到有向图的任意一点距离，初始化起点(first)距离为0，其余点均为MAX (0x3f)，起点入队。
2.判断该点是否存在。（未存在就入队，标记）
3.队首出队，并将该点标记为没有访问过，方便下次入队。
4.遍历以队首为起点的有向边 如果存在更短的距离则更新dist[i]。
5.如果i不在队列中，则入队标记，一直到循环为空。
供选择的答案:
(1) A. q.push(i) B. q.front() C. q.pop() D. q.push(first）
(2) A. to[i] B. dist[first] C. w[i] D. dist[i]
(3) A. dist[j]=dist[now]+w[now]; B. dist[j]= abs(dist[i]+w[now] )
C. dist[j]=dist[now]+w[i] D. dist[j]=dist[i]+w[j]
(4) A. q.push(j) B. q.front() C. q.push(i) D. q.pop(）
(5) A. add() B. spfa(1) C. add(abc) D. spfa()
Input
输入一个整数n, 1<=n<=5，代表题号。
Output
输出选择答案，用大写英文字母表示。
Sample Input Copy
Sample Output Copy