题解来源： 上外三亚附中 周林甫 老师 发表于公众号《科创学习》欢迎大家关注。
这道题目主要考察了图的表示和图的遍历算法。需要根据输入的公路信息构建图，并使用深度优先搜索或广度优先搜索遍历图。
图的表示：使用邻接表或邻接矩阵表示图的结构，以便进行图的遍历。
图的遍历算法：使用深度优先搜索或广度优先搜索算法遍历图，找到满足题目要求的路径或节点。
使用了贪心算法来计算小苞从站点1开车到站点n所需的最少加油费用。
首先，我们使用两个数组v和a来记录站点的信息。数组v记录到当前站点的总路程，数组a记录每个站点的油价。
接下来，我们读取输入的站点数量n和每升油可以让车前进的距离d。
然后，使用一个循环来读取每个站点的距离并计算到当前站点的总路程。注意，我们将路程累加到数组v中，以便后续计算。
接着，使用另一个循环来读取每个站点的油价。
接下来，我们使用贪心算法来计算最少的加油费用。我们使用两个变量mina和nu来记录当前的最低油价和已购买油的体积。
在循环中，我们计算当前需要多少升油，即总路程除以每升油可以前进的距离d。如果有余数，表示需要多买一升油。
然后，我们更新当前的最低油价mina，取当前站点的油价和mina中的较小值。
接着，计算当前需要购买的油的体积。如果需要的油量大于已购买的油量nu，说明需要花钱购买更多的油。
最后，将花费的费用累加到ans中，计算方式为（需要的油量-已购买的油量）乘以当前最低油价。
循环结束后，输出最少的加油费用ans。
使用贪心算法来计算最少的加油费用，通过每次选择当前最低油价来进行加油。
#include <bits/stdc++.h>
using namespace std;
int main() {
// v数组记录到当前站点的总路程，a记录每一站的油价
int n, d, v[10001], a[10001], ans = 0;
cin >> n >> d;
for (int i = 0; i < n - 1; i++) {
cin >> v[i];
if (i != 0)
v[i] += v[i - 1]; // 因为油整升卖，故记录路程和便于计算
}
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int mina = a[0], nu = 0; // mina用于记录当前最低油价，nu记录已购买油的体积
for (int i = 0; i < n - 1; i++) {
int zu = v[i] / d; // 计算当前需要多少升油
if (v[i] % d != 0)
zu++; // 有余数，多买一升
mina = min(mina, a[i]); // 当前最低油价
ans += (zu - nu) * mina; // 最少价钱为（需要的油-已购的油）*当前最低油价
nu = zu; // 花钱了，更新已购油的体积
}
cout << ans;
return 0;
}
方法二：
#include <bits/stdc++.h>
using namespace std;
int n,d;
long long ans=0;
long long v[100005];
long long a[100005];
long long y[100005];
long long youjia;//油价
int main() {
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%d%d",&n,&d);
for (int i=2;i<=n;i++){
scanf("%lld",&v[i]);
v[i]+=v[i-1];//计算站点i到起点的距离
y[i]=ceil(1.0*v[i]/d);//从起点到当前站点的油耗
}
for (int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
youjia=a[1];//出发先在站点1买油
for (int i=2;i<=n;i++){
ans+=youjia*(y[i]-y[i-1]);//增加本段用油的油价
youjia=min(youjia,a[i]);//如果当前站点油比用的油便宜，换成当前站点买
}
cout<<ans;
return 0;
}
