#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)。
输入描述:
第一行输入两个正整数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.