首页 > 试题广场 >

武

[编程题]武
其次，Sεlιнα(Selina) 要进行体力比武竞赛。
在 Sεlιнα 所在的城市，有 个街区，编号为 ，总共有 条的街道连接这些街区， 使得每两个街区之间都直接或间接地有街道将它们相连。Sεlιнα 把通过了文化知识竞赛的参赛男友们召集到她家所在的街区 ，并以这个街区为起点，让所有参赛男友们向其他街区跑去。这些参赛者们被命令不准重复跑某条街道，而且在规定时间内要尽可能地跑远。比赛结束后，所有参赛者将停留在他们此时所在的街区。之后 Sεlιнα 开始视察结果。现在她知道每个街区都有一些她的参赛男友停留着，她现在想先去看看离她家第 近的街区。所以作为一位好帮手，你的任务是要告诉她所有街区中，离 Sεlιнα 家第  近的街区与 Sεlιнα 家之间的距离。 

输入描述:
第一行三个整数，，含义同题面描述。
接下去  行，每行三个整数，，表示从第  个街区到第  个街区有一条权值为 的街道相连。街区从  开始标号。


输出描述:
输出共一行，一个整数，表示所有街区与 Sεlιнα 家所在街区之间最近距离的第  小值。 
示例1

输入

3 3 2
1 2 4
2 3 5

输出

9
示例2

输入

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

输出

7

备注:


算法知识视频讲解
开通博客
头像 黄学骏
发表于 2022-08-05 15:00:14
#include <bits/stdc++.h> using namespace std; const int N = 1e6+10, M = N*2; typedef pair<int,int> PII; int n,p,k; int e[M],ne[M],h[N] 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 小琢卷不动
发表于 2021-11-23 14:56:49
输入的是一个树的结构，她的家在 PPP 点，就以 PPP 为根，dfs 求出每个点到 PPP 的距离 dis\text{dis}dis，然后以 dis\text{dis}dis 来排序，找到离她家第 KKK 远的点即可。 求距离的时候可以用到公式：（假如 uuu 是一个结点，vvv 是 uuu 的孩 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 黑眼圈z
发表于 2023-07-30 15:53:26
题目链接：https://ac.nowcoder.com/acm/problem/15522 就是一道很常规的dijskstra题，虽然我自己debug 疯了（丢脸>_<) #include<bits/stdc++.h> using namespace std; const 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

最短路
难度：
0条回答 28浏览

热门推荐

通过挑战的用户

查看代码

相关试题

武

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号