NOI竞赛试题-------地震(C++)

cuibaowenown2

最下面有EXE文件。
【题目描述】

一座地震频发的山上有N个小村庄，编号分别为1 至N 。某些村庄之间有山路相连，每条山路都有一个防震等级。假如一条路的防震等级是k (k > 0)，就表示如果发生k 级或者小于k 级的地震，这条山路是安然无恙的，但如果发生大于k 级的地震，这条路就会被毁坏，不能通过了。

现在邮递员小明要从村庄1 出发去村庄N ，他想知道最高发生几级地震的情况下，他仍然能顺利到达目的地。

输入数据的第一行是用空格隔开的两个整数N 和M ，分别表示村庄数和山路数(2 ≤N ≤50, 1≤M ≤200)。按下来有M 行，每行包含三个整数u, v, w，表示村庄u 和村庄v 之间有一条防震等级为w 的路(1 ≤u, v ≤N, 1 ≤w ≤20)。路是双向的，在没有被毁坏的情况下，既可以从u 到达v，也可以从v 到达u。两个村庄之间最多有一条路。输入数据保证在没有发生的地震的时候可以从村庄1 到达村庄N 。

输出只有一行，包含一个整数，表示最高发生几级地震的情况下仍然能到达村庄N 。

【样例输入】

4 5
1 2 3
1 3 5
2 4 10
3 4 6
1 4 1

【样例输出】

5

【样例解释】

在发生5 级地震的情况下，小明可以通过1 →3 →4 这条路线到达村庄4。但如果发生6 级
地震就不能到达了。


答案：

游客，如果您要查看本帖隐藏内容请回复

Earthquake.rar (16.17 KB, 下载次数: 0, 售价: 1 鱼币)

2012-1-8 18:50 上传

点击文件名下载附件

祇逑_铵乐

用图的知识可以解决啊。就像求最短路径一样

cuibaowenown2

祇逑_铵乐 发表于 2012-1-9 23:04

                               
登录/注册后可看大图

用图的知识可以解决啊。就像求最短路径一样

额，图还不会

sky!

see see。。。。。。。