题意分析

题目要求构建一棵以节点$1$为根的树，使得总成本最小。每条边的成本计算公式为：

通过分析可以发现，每个节点的贡献可以转化为：

因此，问题转化为：

1. 计算每个节点到根节点$1$的最短路径
2. 若存在节点不可达，则输出"No Answer"
3. 否则，计算所有节点贡献的总和

解题思路

1. 图建模：将问题转化为有向图，节点为树的节点，边为可能的连接方式
2. 最短路径：使用Dijkstra算法计算从根节点$1$到所有其他节点的最短路径
3. 贡献计算：对每个节点，将其权重乘以最短路径长度，累加得到总成本
4. 特殊情况处理：若存在节点不可达，则输出"No Answer"

实现步骤

1. 输入处理：读取节点数$v$和边数$e$，以及各节点权重和边信息
2. 建图：使用邻接表存储图结构
3. 最短路径计算：使用优先队列优化的Dijkstra算法
4. 结果计算：遍历所有节点，计算总成本
5. 输出结果：根据可达性输出结果

C++实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii;
const int INF = INT_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        int v, e;
        cin >> v >> e;
        vector<int> w(v+1);
        for (int i = 1; i <= v; ++i) {
            cin >> w[i];
        }
        
        vector<vector<pii> > adj(v+1);
        for (int i = 0; i < e; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            adj[a].push_back(make_pair(b, c));
            adj[b].push_back(make_pair(a, c));
        }
        
        vector<int> dist(v+1, INF);
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        dist[1] = 0;
        pq.push(make_pair(0, 1));
        
        while (!pq.empty()) {
            pii top = pq.top();
            pq.pop();
            int d = top.first;
            int u = top.second;
            if (d > dist[u]) continue;
            for (size_t i = 0; i < adj[u].size(); ++i) {
                int v = adj[u][i].first;
                int c = adj[u][i].second;
                if (dist[v] > dist[u] + c) {
                    dist[v] = dist[u] + c;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
        
        bool possible = true;
        long long total = 0;
        for (int i = 1; i <= v; ++i) {
            if (dist[i] == INF) {
                possible = false;
                break;
            }
            total += w[i] * dist[i];
        }
        
        if (possible) {
            cout << total << "\n";
        } else {
            cout << "No Answer\n";
        }
    }
    
    return 0;
}

代码说明

1. 输入优化：使用ios::sync_with_stdio(false)和cin.tie(nullptr)加速输入输出
2. 数据结构：
   • 使用vector<vector<pii>>存储邻接表
   • 使用优先队列实现Dijkstra算法
3. 算法流程：
   • 初始化所有节点距离为无穷大
   • 从根节点$1$开始，使用Dijkstra算法计算最短路径
   • 检查所有节点是否可达
   • 计算总成本并输出
4. 时间复杂度：$O(E \log V)$，适合处理题目给定的数据规模