#4683. 路线(2022年4月省赛第二场)

路线(2022年4月省赛第二场)

Background

第五题(难度系数 5,满分80分)

编程实现:路线

题目描述:

有一个旅游景区,景区中有N个景点,景点以数字1到N编号,其中编号为N的景点为游客服务中心所在地。景区中有M条连接路线,每条路线连接两个景点。

已知:

1)一个景点可以被多条路线连接;

2)景点之间的连接路线都可以双向行走;

当给出N个景点和M条连接路线,及M条路线的连接关系,请你计算出从编号1到编号N-1的每一个景点,到达游客服务中心至少需要经过几条路线,如果某个景点不能到达游客服务中心则输出“-1”。

例如:N=5,M=4,4条路线的连接关系为:1<->2、1<->3、2<->4、2<->5,

景点1到达景点5(游客服务中心)至少经过2条路线(路线2,路线4);

景点2到达景点5(游客服务中心)至少经过1条路线(路线4);

景点3到达景点5(游客服务中心)至少经过3条路线(路线1,路线2,路线4);

景点4到达景点5(游客服务中心)至少经过2条路线(路线3,路线4)。 image 输入描述:

第一行输入两个正整数N和M(4≤N≤100,1≤M≤100),N表示景点个数,M表示路线条数,两个正整数之间一个空格隔开

接下来输入M行,每行包含两个正整数S,E(1≤S≤N,1≤E≤N,S≠E),两个正整数之间一个空格隔开,表示编号S和编号E的两个景点有一条路线连接

输出描述:

一行输出多个整数。按照1到N-1的编号顺序,分别输出每个景点到达编号N(游客服务中心),至少经过几条路线可以到达,如果某个景点不能到达则输出“-1”,整数之间一个空格隔开

样例输入:

5 4

1 2

1 3

2 4

2 5

样例输出:

2 1 3 2

评分标准:

20分:能正确输出一组数据;

20分:能正确输出两组数据;

20分:能正确输出三组数据;

20分:能正确输出四组数据。

Limitation

1s, 1024KiB for each test case.