title: 2019牛客国庆集训派对 H-Highway (dijk求树的直径（当然还有更优的）)

categories: 2019牛客国庆集训派对

top: false

tags:

  • acm

  • 树的直径

题目大意

题目链接

n个点从1-n, 有(n - 1)条边连接。

现在要重新修（n - 1）条路， 修i 到 j 所用的代价为i到j的最短路，

问最多的代价是多少

分析

就是求树的直径， 然后跑两边最短路求其他点到直径两端点的最短路， 最后把最大值加起来就可。

AC代码

#include 

using namespace std;

typedef long long ll;

typedef pair P;

const int INF = 0x3f3f3f3f;

const ll llINF = 0x3f3f3f3f3f3f3f3f;

const int mod = int(1e9) + 7;

const int N = int(1e5) + 10;

struct edge{

int u, v, ne;

ll w;

}ed[2 * N];

int n, cnt, head[N];

ll dis1[N], dis2[N];

bool vis[N];

void init(){

cnt = 0;

memset(head, -1, sizeof head);

}

void add(int u, int v, ll w){

ed[cnt].u = u, ed[cnt].v = v, ed[cnt].w = w, ed[cnt].ne = head[u];

head[u] = cnt++;

}

int dijk(ll dis[], int st){

for (int i = 1; i <= n; i++)

dis[i] = ll(1e15);

memset(vis, false, sizeof vis);

priority_queue, greater >q;

dis[st] = 0;

q.emplace(0, st);

while(!q.empty()){

int u = q.top().second;

q.pop();

if (vis[u]) continue;

vis[u] = 1;

for (int i = head[u]; ~i; i = ed[i].ne){

int v = ed[i].v;

if (dis[v] > dis[u] + ed[i].w){

dis[v] = dis[u] + ed[i].w;

q.emplace(dis[v], v);

}

}

}

ll ans = 0, ansj;

for (int i = 1; i <= n; ++i){

if (dis[i] != ll(1e15) && dis[i] > ans){

ans = dis[i], ansj = i;

}

}

return ansj;

}

int main() {

std::ios::sync_with_stdio(0);

int a, b;

ll c;

while(cin >> n){

init();

for (int i = 0; i < n - 1; ++i){

cin >> a >> b >> c;

add(a, b, c);

add(b, a, c);

}

int s1 = dijk(dis1, 1);

int s2 = dijk(dis1, s1);

dijk(dis1, s1);

dijk(dis2, s2);

ll ans = dis1[s2];

for (int i = 1; i <= n; i++){

if (i == s1 || i == s2)

continue;

ans += max(dis1[i], dis2[i]);

}

cout << ans <<"\n";

}

return 0;

}

、

恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。 --mingfuyan