Gym - 100004A 树的性质

题目：

题意：

从节点 0 出发，把每一个节点都经过一遍，然后从一个节点回到学校。

由于有 n+1个节点，n条边，而且保证两两互相到达，那么这就是一个棵树。

于是，可以发现，如果从一个点出发，然后回到原来的点，路程是所有边的2倍，这样，就可以枚举从哪个点回学校就行了。

然后一个坑点就是，那个最后枚举的时候ans初始化要注意很大，因为每条边的权值都是10的9次方大小。

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <queue>

 using namespace std;

 const int maxn = ;

 int times[maxn];

 struct Edge {

     int from,to;

     long long dist;

 };

 struct Hope {

     int u;

     long long d;

     bool operator < (const Hope& rhs) const {

         return d > rhs.d;

     }

 };

 struct Dij {

     int n,m;

     vector<int> G[maxn];

     vector<Edge> edges;

     bool vis[maxn];

     long long d[maxn];

     void init(int n) {

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

             G[i].clear();

         edges.clear();

     }

     void AddEdge (int from,int to,long long dist) {

         edges.push_back((Edge){from,to,dist});

         m = edges.size();

         G[from].push_back(m-);

     }

     void dij(int s) {

         memset(vis,,sizeof(vis));

         memset(d,0x3f3f3f3f,sizeof(d));

         d[s] = ;

         //vis[s] = 1;

         priority_queue<Hope> Q;

         Q.push((Hope){s,});

         while(!Q.empty()) {

             Hope x = Q.top();Q.pop();

             if(vis[x.u])

                 continue;

             vis[x.u] = true;

             for(int i=;i<G[x.u].size();i++) {

                 Edge& e = edges[G[x.u][i]];

                 if(d[e.to]>d[x.u]+e.dist) {

                     d[e.to] = d[x.u] + e.dist;

                     Q.push((Hope){e.to,d[e.to]});

                 }

             }

         }

     }

 };

 Dij sol;

 int main(int argc, char** argv) {

     int n;

     scanf("%d",&n);

     sol.init(n+);

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

         scanf("%lld",&times[i]);

     long long sum = ;

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

         int from,to;

         long long dist;

         scanf("%d%d%lld",&from,&to,&dist);

         sum+=dist;

         sol.AddEdge(from,to,dist);

         sol.AddEdge(to,from,dist);

     }

     sol.dij();

     sum*=;

     long long ans = ;

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

         ans = min(ans,sum-sol.d[i]+(long long)times[i]);

     }

     printf("%lld\n",ans);

     return ;

 }