ccf 201503-5 最小花费 这题交上去只有10分嗨！求大佬的题解啊

问题描述

　　C国共有n个城市。有n-1条双向道路，每条道路连接两个城市，任意两个城市之间能互相到达。小R来到C国旅行，他共规划了m条旅行的路线，第i条旅行路线的起点是s，终点是t。在旅行过程中，小R每行走一单位长度的路需要吃一单位的食物。C国的食物只能在各个城市中买到，而且不同城市的食物价格可能不同。
　　然而，小R不希望在旅行中为了购买较低价的粮食而绕远路，因此他总会选择最近的路走。现在，请你计算小R规划的每条旅行路线的最小花费是多少。

输入格式

　　第一行包含2个整数n和m。
　　第二行包含n个整数。第i个整数w表示城市i的食物价格。
　　接下来n-1行，每行包括3个整数u, v, e，表示城市u和城市v之间有一条长为e的双向道路。
　　接下来m行，每行包含2个整数s和t，分别表示一条旅行路线的起点和终点。

输出格式

　　输出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 ≤ 20；
　　前30%的评测用例满足：n, m ≤ 200；
　　另有40%的评测用例满足：一个城市至多与其它两个城市相连。
　　所有评测用例都满足：1 ≤ n, m ≤ 10，1 ≤ w ≤ 10，1 ≤ e ≤ 10000。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

vector<pair<int,int> > ss[100000+1];

int cost[100000+1];

int visited[100000+1];

ll c,mc,ml,l;

int t;

void dfs(int m,int n)

{

    if(m==n)

    {

        mc=min(c,mc);

        return;

    }

    for(int i=0;i<ss[m].size();i++)

    {

        int a=ss[m][i].first,b=ss[m][i].second;

        if(!visited[a])

        {

            if(c+b*t>mc)continue;

            if(l+b>ml)continue;

            int fc=c,fl=l,ft=t;

            visited[a]=1;c+=b*t;

            l+=b;t=min(t,cost[a]);

            dfs(a,n);

            visited[a]=0;c=fc;l=fl;t=ft;

        }

    }

}

int main()

{

    int n,m;cin>>n>>m;

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

    {

        cin>>cost[i];

    }

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

    {

        int u,v,e;cin>>u>>v>>e;

        ss[u].push_back(make_pair(v,e));

        ss[v].push_back(make_pair(u,e));

    }

    while(m--)

    {

        int start,en;cin>>start>>en;

        int d[n+1];memset(d,127,sizeof(d));

        int vis[n+1]={0};

        priority_queue<pair<int,int> > s;

        while(!s.empty())s.pop();

        s.push(make_pair(0,start));

        while(!s.empty())

        {

            int v=s.top().second;s.pop();

            if(v==en)break;

            if(vis[v])continue;

            vis[v]=1;

            for(int i=0;i<ss[v].size();i++)

            {

                int node=ss[v][i].first,len=ss[v][i].second;

                if(!vis[node])

                {

                    if(len+d[v]<d[node])

                    {

                        d[node]=len+d[v];

                        s.push(make_pair(-d[node],node));

                    }

                }

            }

        }

        ml=d[en];c=0;

        mc=ml*cost[start];

        memset(visited,0,sizeof(visited));

        l=0;t=cost[start];

        visited[start]=1;

        dfs(start,en);

        cout<<mc<<endl;

    }

    return 0;

}