问题描述 　　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。 
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long int n,m;
 4 long int a[10005];
 5 struct edge
 6 {
 7     long int a,b;
 8 };
 9 long int cost,mincost,c[10005],sw;
10 vector<vector<edge> > b(10005);
11 long int visited[10001];
12 void dfs(long int s,long int t)
13 {
14     if(s==t)
15     {
16         mincost=min(cost,mincost);
17         return ;
18     }
19     c[s]=sw;
20     sw=min(sw,a[s]);
21     visited[s]=1;
22     for(int i=0;i<b[s].size();i++)
23     {
24         edge v=b[s][i];
25         if(visited[v.a]==0)
26         {
27             if(cost+sw*v.b>mincost)
28                 continue;
29             cost+=sw*v.b;
30             dfs(v.a,t);
31             cost-=sw*v.b;
32         }
33     }
34     sw=c[s];
35     visited[s]=0;
36 }
37 int main()
38 {
39     scanf("%ld%ld",&n,&m);
40     for(int i=1;i<n+1;i++)
41     {
42         scanf("%ld",&a[i]);
43     }
44     long int result[m+5],k=0;
45     while(n-->1)
46     {
47         long int u,v,e;
48         scanf("%ld%ld%ld",&u,&v,&e);
49         edge c;
50         c.a=v;c.b=e;
51         b[u].push_back(c);
52         c.a=u;
53         b[v].push_back(c);
54     }
55     while(m--){
56     int s,t;
57     scanf("%d%d",&s,&t);
58     memset(visited,0,sizeof(visited));
59     cost=0;mincost=1<<30;sw=1<<30;
60     dfs(s,t);
61     result[++k]=mincost;
62 }
63     for(int i=1;i<=k;i++)
64     {
65         printf("%ld\n",result[i]);
66     }
67     return 0;
68 }

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

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。