ccf 201503-5 最小花费 (10分)。。。


问题描述
  C国共有n个城市。有n-1条双向道路,每条道路连接两个城市,任意两个城市之间能互相到达。小R来到C国旅行,他共规划了m条旅行的路线,第i条旅行路线的起点是si,终点是ti。在旅行过程中,小R每行走一单位长度的路需要吃一单位的食物。C国的食物只能在各个城市中买到,而且不同城市的食物价格可能不同。
  然而,小R不希望在旅行中为了购买较低价的粮食而绕远路,因此他总会选择最近的路走。现在,请你计算小R规划的每条旅行路线的最小花费是多少。
输入格式
  第一行包含2个整数n和m。
  第二行包含n个整数。第i个整数wi表示城市i的食物价格。
  接下来n-1行,每行包括3个整数u, v, e,表示城市u和城市v之间有一条长为e的双向道路。
  接下来m行,每行包含2个整数si和ti,分别表示一条旅行路线的起点和终点。
输出格式
  输出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, wi≤ 20;
  前30%的评测用例满足:n,m≤ 200;
  另有40%的评测用例满足:一个城市至多与其它两个城市相连。
  所有评测用例都满足:1 ≤n,m≤ 105,1 ≤ wi≤ 106,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;
}

长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号