最短路板题。
乘坐的过程一定是先车再火车（如果有），假设换车地点为 \(x\)，那么最小代价为坐车从 \(1\) 到 \(x\) 与坐火车从 \(x\) 到 \(n\) 的最小代价之和，分开跑最短路即可，时间复杂度 \(O(n^2\log n+n)\)。
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define int long long
using namespace std;
const long long linf=9223372036854775807;
const int N=1000+10;
int n,a,b,c,dist[N][N],lst[N],d1[N],d2[N],ans=linf;
bool vis[N];
struct node{int v,w;};
vector<node> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
void dij(int x)
{
memset(vis,0,sizeof(vis));
q.push(make_pair(0,x));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int v=1;v<=n;v++)
{
if(u==v)continue;
int w=(x==1?dist[u][v]*a:dist[u][v]*b+c);
if(x==1&&d1[v]>d1[u]+w)
{
d1[v]=d1[u]+w;
q.push(make_pair(d1[v],v));
}
if(x==n&&d2[v]>d2[u]+w)
{
d2[v]=d2[u]+w;
q.push(make_pair(d2[v],v));
}
}
}
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
memset(d1,127,sizeof(d1));
memset(d2,127,sizeof(d2));
d1[1]=0;
d2[n]=0;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&dist[i][j]);
dij(1),dij(n);
for(int i=1;i<=n;i++)ans=min(ans,d1[i]+d2[i]);
printf("%lld",ans);
}