C++14(g++5.4) 解法, 执行用时: 114ms, 内存消耗: 8648K, 提交时间: 2020-10-06 20:24:35

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;

int n, p, k;
int u, v, w;
int dis[maxn];
vector<pair<int, int> > g[maxn];
void dfs(int s, int pre) {
	for(int i = 0; i < g[s].size(); i++) {
		int next = g[s][i].first;
		if(next != pre) {
			dis[next] = dis[s] + g[s][i].second;
			dfs(next, s);
		}
	}
}
int main() {
	cin >> n >> p >> k;
	for(int i = 0; i < n - 1; i++) {
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dfs(p, 0);
	sort(dis + 1,dis + n + 1);
	cout << dis[k+1];
	system("pause");
	return 0;
}
 

C++(clang++ 11.0.1) 解法, 执行用时: 112ms, 内存消耗: 8556K, 提交时间: 2023-04-20 21:11:25

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
struct edge
{
	int v,w;
};
vector<edge>g[maxn];
int dis[maxn];
bool vis[maxn];
void dfs(int x)
{
	vis[x]=true;
	for(auto e:g[x])
	{
		if(vis[e.v]) continue;
		dis[e.v]=dis[x]+e.w;
		dfs(e.v);
	}
}
int main()
{
	int n,p,k;
	cin>>n>>p>>k;
	int u,v,w,m=n-1;
	while(m--)
	{
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
		g[v].push_back((edge){u,w});
	}
	dfs(p);
	sort(dis+1,dis+n+1);
	cout<<dis[k+1];
	return 0;
}

Python(2.7.3) 解法, 执行用时: 1242ms, 内存消耗: 42740K, 提交时间: 2018-04-21 20:57:59

n, p, k = map(int, raw_input().split())
g = {}
d = [0] * (n + 1)


def dfs(n, father):
    for nxt, weight in g[n]:
        if nxt != father:
            d[nxt] = d[n] + weight
            dfs(nxt, n)


for _ in xrange(n - 1):
    u, v, w = map(int, raw_input().split())
    g.setdefault(u, []).append((v, w))
    g.setdefault(v, []).append((u, w))
dfs(p, -1)
print sorted(d)[k + 1]

Python3 解法, 执行用时: 594ms, 内存消耗: 41452K, 提交时间: 2022-08-17 09:36:42

n, p, k = map(int, input().split())
e=[[] for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    e[u-1].append((v-1,w))
    e[v-1].append((u-1,w))
d=[10**10]*n
d[p - 1] = 0
def dfs(u,f):
    for (v,w) in e[u]:
        if v != f:
            d[v]=d[u] + w
            dfs(v,u)
dfs(p-1,-1)
d.sort()
print(d[k])