P3406 海底高铁

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int n,m;
int p[N];
long long d[N];int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=m;i++) cin>>p[i];for(int i=1;i<m;i++){int u=min(p[i],p[i+1]);int v=max(p[i],p[i+1]);d[u]+=1;d[v]-=1;}for(int i=1;i<=n;i++) d[i]+=d[i-1];long long ans=0;for(int i=1;i<=n-1;i++){int a,b,c;cin>>a>>b>>c;ans+=min(d[i]*a,d[i]*b+c);}cout<<ans<<endl;return 0;
}