大臣の旅費連絡ブロック【ブルーブリッジ真題】(c++)

試験問題大臣の旅費
について述べる
資源制限時間制限:1.0 sメモリ制限:256.0 MBの問題記述はずっと前、T王国は空前の繁栄を遂げた.国をよりよく管理するために、王国は首都と王国内の各都市を結ぶために多くの高速道路を建設した.
経費を節約するために、T国の大臣たちは考え、どの大都市も首都から直接または他の大都市を通じて間接的に到着できるように、優れた建設案を制定した.また、大都市を繰り返さなければ、首都から各大都市に到着する案が唯一だ.
JはT国の重要大臣で、各都市の間を巡察し、民情を察した.だから、ある都市から別の都市へ行くのがJの最もよくあることになった.彼は都市間を行き来する旅費を預けるための財布を持っている.
聡明なJは、ある都市で立ち止まって整備しなければ、連続走行の過程で、彼が使った旅費は彼が歩いた距離と関係があり、xキロ目からx+1キロ目までの千メートル(xは整数)で、彼が使った旅費はx+10ほどあることを発見した.つまり、1キロ歩くと11、2キロ歩くと23がかかります.
J大臣は、ある都市を出発して、途中で休まずに別の都市に着いたが、かかる可能性のあるすべての道路費の中で最大いくらだったか知りたいと思っています.
入力フォーマット入力の最初の行には、首都を含むT王国の都市数を表す整数nが含まれています.
都市は1から順に番号付けされ、1番都市は首都です.
次にn-1行、T国の高速道路(T国の高速道路は必ずn-1本)について説明する
行ごとに3つの整数Pi,Qi,Diがあり、都市Piと都市Qiの間に高速道路があり、長さはDiキロであることを示している.
出力フォーマットは、大臣Jが最も多く費やした道路費がいくらであるかを示す整数を出力する.
サンプル入力5 1 2 2 1 3 1 2 4 5 4サンプル出力135出力フォーマット大臣Jは都市4から都市5まで135の旅費を費やす.
私の考え

実現参考:連通思想

アルゴリズム一覧

#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
 
using namespace std;
 
typedef long long ll;
const int maxn = 1000000;
int head[maxn],cnt,vis[maxn];
ll dist;
struct Edge{
    int v,nex;
    ll w;
}edge[maxn*2];

typedef struct Node {
    int x;
    ll dis;
}node;

void addEdge(int u,int v,ll w) {
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt++;
 
    edge[cnt].v = u;
    edge[cnt].w = w;
    edge[cnt].nex = head[v];
    head[v] = cnt++;
}

int bfs(int Start) {
    int source;
    node cur,nex;
    memset(vis,0,sizeof(vis));
    queue<node>qu;
    cur.x = Start;
    cur.dis = 0;
    vis[Start] = 1;
    qu.push(cur);
    dist = 0;
    source = Start;
    int a,b;
    while(!qu.empty()) {
        cur = qu.front();
        qu.pop();
        a = cur.x;
        if(cur.dis > dist) {
            dist = cur.dis;
            source = a;
        }
        int i;
        for(i=head[a]; i!=-1; i=edge[i].nex) {
            b = edge[i].v;
            if(vis[b]==0) {
                vis[b] = 1;
                nex.x = b;
                nex.dis = cur.dis + edge[i].w;
                qu.push(nex);
            }
        }
    }
    return source;
}

int main() {
    int n,u,v;
    ll w;
    //~       ，   ~scanf("%d",&n)    scanf("%d",&n)！=-1,        。 
    while(~scanf("%d",&n)) {
        cnt = 0;
        memset(head,-1,sizeof(head));//     
        for(int i = 1; i < n; i++) {
            scanf("%d%d%lld",&u,&v,&w);
            addEdge(u,v,w);
        }
        int newStart = bfs(1); //           ，     1
        bfs(newStart);         //  1    newStart    newStart    。
        ll ans;
        //                。
        if(dist%2==0) {
            ans = dist/2;
            ans = ans*(dist+1);
        }
        else {
            ans = (dist+1)/2;
            ans = ans*dist;
        }
        ans += dist*10;
        printf("%lld
",ans);
    }
    return 0;
}

上記リンク:最大スケール公約数多重【ブルーブリッジ真題】(c++)