试题编号：	201503-5
试题名称：	最小花费
时间限制：	4.0s
内存限制：	256.0MB
问题描述：	问题描述 　　C国共有n个城市。有n-1条双向道路，每条道路连接两个城市，任意两个城市之间能互相到达。小R来到C国旅行，他共规划了m条旅行的路线，第i条旅行路线的起点是s i，终点是t i。在旅行过程中，小R每行走一单位长度的路需要吃一单位的食物。C国的食物只能在各个城市中买到，而且不同城市的食物价格可能不同。 　　然而，小R不希望在旅行中为了购买较低价的粮食而绕远路，因此他总会选择最近的路走。现在，请你计算小R规划的每条旅行路线的最小花费是多少。 输入格式 　　第一行包含2个整数n和m。 　　第二行包含n个整数。第i个整数w i表示城市i的食物价格。 　　接下来n-1行，每行包括3个整数u, v, e，表示城市u和城市v之间有一条长为e的双向道路。 　　接下来m行，每行包含2个整数s i和t i，分别表示一条旅行路线的起点和终点。 输出格式 　　输出m行，分别代表每一条旅行方案的最小花费。 样例输入 6 4 1 7 3 2 5 6 1 2 4 1 3 5 2 4 1 3 5 2 3 6 1 2 5 4 6 6 4 5 6 样例输出 35 16 26 13 样例说明 　　对于第一条路线，小R会经过2->1->3->5。其中在城市2处以7的价格购买4单位粮食，到城市1时全部吃完，并用1的价格购买7单位粮食，然后到达终点。 评测用例规模与约定 　　前10%的评测用例满足：n, m ≤ 20, w i ≤ 20； 　　前30%的评测用例满足：n, m ≤ 200； 　　另有40%的评测用例满足：一个城市至多与其它两个城市相连。 　　所有评测用例都满足：1 ≤ n, m ≤ 10 5，1 ≤ w i ≤ 10 6，1 ≤ e ≤ 10000。

问题链接：。

原题链接：。

问题描述：参见上文。

问题分析：这是一个图的算法问题。n个结点n-1条边，任意两个结点都相互联通，说明是一个树，即任意两点之间只有一条唯一的通路。可以用DFS来寻找一个从起点到终点的通路，算出最小花费，但是过于费时间，只得了30分。这个需要从算法上进行彻底的改进！这个解法的问题在于需要求得起点到终点得对<src,dest>多的时候，需要每次都做一次DFS，总体上时间复杂度过高。

程序说明：程序中，图用邻接表表示。对于输入的m对起点和终点，分别用DFS寻找它们之间的路径，然后算出最小花费。

提交后得30分的程序如下：

/* CCF201503-5 最小花费 */#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef unsigned long long ULL;const int MAXN = 100000;ULL price[MAXN+1];int visited[MAXN+1];struct adjacency {    int node, edge;    adjacency(int n, int e) { node = n; edge = e;}};vector
       
         g[MAXN+1];struct node {    int node, edge;};int N, M;ULL ans;bool endflag;void dfs(int node, int end, ULL miniprice){    ULL currprice;    ULL cost;    if(node == end) {        cout << ans << endl;        endflag = true;        return;    } else {        visited[node] = 1;        for(int i=0; i<(int)g[node].size() && !endflag; i++) {            if(!visited[g[node][i].node]) {                currprice = min(miniprice, price[node]);                cost = g[node][i].edge * currprice;                ans += cost;                dfs(g[node][i].node, end, currprice);                ans -= cost;            }        }    }}int main(){    int u, v, e;    // 输入数据    cin >> N >> M;    for(int i=1; i<=N; i++)        cin >> price[i];    for(int i=1; i<=N-1; i++) {        cin >> u >> v >> e;        g[u].push_back(adjacency(v, e));        g[v].push_back(adjacency(u, e));    }    // 输入起点和终点，用DFS计算最小花费，并且输出结果    int start, end;    for(int i=0; i
        
         > start >> end;        memset(visited, 0, sizeof(visited));        endflag = false;        ans = 0;        dfs(start, end, price[start]);    }    return 0;}
        
       
      
     
    

参考题解（100分）：。

参考题解（这个解法似乎更加有效）：。