問題鏈接：CCF201503試題。

原題鏈接：最小花費。

問題描述：參見上文。

問題分析：這是一個圖的算法問題。n個結點n-1條邊，任意兩個結點都相互聯通，說明是一個樹，即任意兩點之間只有一條唯一的通路。可以用DFS來尋找一個從起點到終點的通路，算出最小花費，但是過于費時間，只得了30分。這個需要從算法上進行徹底的改進！這個解法的問題在于需要求得起點到終點得對<src,dest>多的時候，需要每次都做一次DFS，總體上時間復雜度過高。

程序說明：程序中，圖用鄰接表表示。對于輸入的m對起點和終點，分別用DFS尋找它們之間的路徑，然后算出最小花費。

提交后得30分的C++語言程序如下：

/* CCF201503-5 最小花費 */#include <iostream>#include <cstring>#include <vector>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<adjacency> 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<M; i++) {        cin >> start >> end;        memset(visited, 0, sizeof(visited));        endflag = false;        ans = 0;        dfs(start, end, price[start]);    }    return 0;}
參考題解（100分）：第四屆CCF軟件能力認證 第五題（最小花費）題解。
參考題解（這個解法似乎更加有效）：第四屆CCF軟件能力認證(CSP2015) 第五題（最小花費）題解。