[ABC222] F - Expensive Expense

[Q] https://atcoder.jp/contests/abc222/tasks/abc222_f
観光費用を含めた直径を求めたら、両端のどちらかから訪れるのが最大費用になる。ようだ…。すごい。

解説をよく読む。
https://atcoder.jp/contests/abc222/editorial/2749

ダイクストラを行うのは距離だけでいい。
直径の判断時に、距離+Dで判定するだけ。
実装。

struct edge{ll to, cost;};
typedef pair<ll, ll> P;
struct graph{
 ll V;
 vector<vector<edge>> G;
 vector<ll> d;
 vector<ll> prev;
 vector<bool> used;

 graph(ll n){
   init(n);
 }

 void init(ll n){
   V = n;
   G.resize(V);
   d.resize(V);
   prev.resize(V);
   used.resize(n);
   rep(i, n) used[i] = false;
 }

 void add_edge(ll s, ll t, ll cost){
   edge e;
   e.to = t, e.cost = cost;
   G[s].push_back(e);
 }

 void del_edge(ll s, ll t, ll cost){
   for (auto it = G[s].begin(); it != G[s].end();){
     if ((*it).to == t && (*it).cost == cost)
       it = G[s].erase(it);
     else
       it++;
   }
 }

 ll get_edgesize(ll s){
   ll size = 0;
   for(auto v: G[s]){
     if (used[v.to]) continue;
     used[v.to] = true;
     size++;
     size += get_edgesize(v.to);
   }
   return size;
 }
 
 //経路はprevに
 void dijkstra(ll s){
   rep(i, V){
     d[i] = oo;
     prev[i] = -1;
   }
   d[s] = 0;
   priority_queue<P, vector<P>, greater<P>> que;
   que.push(P(0, s)); //cost, v
   while(!que.empty()){
     P p = que.top(); que.pop();
     ll v = p.second;
     if(d[v] < p.first) continue;
     for(auto e : G[v]){ //e=next, cost
       if(d[e.to] > d[v] + e.cost){
         d[e.to] = d[v] + e.cost;
         que.push(P(d[e.to], e.to));
         prev[e.to] = v; //vからe.toについた
       }
     }
   }
 }  
 
 vector<ll> get_path(int g, int s) {
   // s 1->2->3 g
   // path[0]=1 path[1]=2 path[2]=3 を返す
   vector<ll> path;
   for (int cur = g; cur != s; cur = prev[cur]) { // goalまで
       path.push_back(cur);
   }
   path.push_back(s);
   reverse(path.begin(), path.end()); // 逆順なのでひっくり返す
   return path;
 }
};

int main(){
 cin.tie(0);
 ios::sync_with_stdio(0);
 cout << fixed << setprecision(10);
 
 ll N;
 cin >> N;
 graph g(N+1); // 0index ~ 
 rep(i, N-1){
   ll A, B, C;
   cin >> A >> B >> C;
   --A;
   --B;
   g.add_edge(A, B, C);
   g.add_edge(B, A, C);
 }
 ll D[N];
 rep(i, N) cin >> D[i];
 //直径だしたい。とりあえず0
 g.dijkstra(0);
 ll _d=0;
 ll s=-1, t=-1;
 ll sdis[N], tdis[N];
 rep(i, N){
   if (chmax(_d, g.d[i]+D[i])) s=i;
 }
 // sから。t出したい
 _d=0;
 g.dijkstra(s);
 rep(i, N){
   if (i!=s && chmax(_d, g.d[i]+D[i])) t=i; // D[s]がとても大きい場合、s->sになる場合がある。例2。
   sdis[i] = g.d[i];
 }
 //s->t
 g.dijkstra(t);
 rep(i, N) tdis[i] = g.d[i];
 
 // i->s or i->tが解答候補
 rep(i, N){
   ll ans = 0;
   if (i!=s) chmax(ans, sdis[i]+D[s]); // i->s
   if (i!=t) chmax(ans, tdis[i]+D[t]); // i->t
   cout << ans << endl;
 }
}

https://atcoder.jp/contests/abc222/submissions/26492128