牛客练习赛24---D
名字挺有意思的,排插树,虽然这是个图。算dijkstra的模版题,求最短路里面最长的那条,因为到讲台的距离总是取决于最短的那条路,但是又要求离讲台最远,那么我们通过dijkstra计算出起始点到所有点的最短路然后遍历找最大值就好。
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;
const int maxn = 1e6 + 10;
const int maxx = maxn*2;
struct node {
int to,nex,w;
}edge[maxx];
int head[maxn],dis[maxn],in[maxn];
int cnt,n,m,u,v,w;
void add(int u,int v,int w){
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].nex = head[u];
head[u] = cnt++;
}
void dijkstra(int s,int dis[]){
priority_queue<pi> pq;
for (int i=1; i<=n; i++)
dis[i] = 99999999;
dis[s] = 0;
pq.push(make_pair(0,s));
while (!pq.empty()) {
pi now = pq.top();pq.pop();
int u = now.second;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].to;
if (dis[v] > dis[u] + edge[i].w){
dis[v] = dis[u] + edge[i].w;
pq.push(make_pair(dis[v],v));
}
}
}
}
int main(){
scanf("%d",&n);
memset(head, -1, sizeof(head));
for (int i=0; i<n-1; i++) {
scanf("%d%d%d",&v,&u,&w);
add(u, v, w);
in[v]++;
}
int s = 0;
for (int i=1; i<=n; i++) {
if (in[i] == 0) {s = i; break;}
}
//cout << s << endl;
dijkstra(s, dis);
int ans = 0;
for (int i=1; i<=n; i++) {
// cout << dis[i] << ' ' ;
if (dis[i] > ans && dis[i] != 99999999){
ans = dis[i];
}
}
printf("%d\n",ans);
return 0;
}