分层图 + dijkstra 

关键点:第一层的点对于第二层来说是有向图 第二层无法返回第一层 构建这样的分层图
两倍的点 两倍多的边（可以开三倍） 然后套dijkstra堆优化模板 注意输出的距离是dist[2 * n]
所有的x点都能到达x + n因此 dist[x + n]这个点的含义才是到点1的最短路
dist[x]是只坐车最短路

代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2020, M = 2e6 + 10;
#define x first
#define y second
typedef long long ll;
typedef pair<ll, ll>pii;
ll n, a, b, c;
ll e[M], h[M], w[M], ne[M], idx;
ll dist[N];
bool st[N];

void add(ll a, ll b, ll c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void jks()
{
    priority_queue<pii, vector<pii>, greater<pii>>heap;
    heap.push({0, 1});

    memset(dist, 0x3f ,sizeof dist);
    dist[1] = 0;

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        ll no = t.y;

        if(st[no])continue;
        st[no] = true;
        // cout << no <<endl;
        for(ll i = h[no];i != -1;i = ne[i])
        {
            ll j = e[i];

            if(dist[j] > dist[no] + w[i])
            {
                dist[j] = dist[no] + w[i];
                // cout << dist[no] << " " << w[i] << endl;
                heap.push({dist[j], j});
            }
        }

        // for(int i = 1;i <= 2 * n;i++)cout << dist[i] <<" ";
        // cout <<endl;
    }
}

int main()
{
    ios::sync_with_stdio;
    cin.tie(0);
    cout.tie(0);

    cin >> n >> a >> b >> c;
    memset(h, -1, sizeof h);

    for(int i = 1;i <= n;i++)
    for(int j = 1;j <= n;j++)
    {
        ll t;
        cin >> t;
        if(i == j)continue;
        add(i, j, a * t);
        add(i + n, j + n, b * t + c);
        add(i, i + n, 0);
    }

    // for(int i = h[5];i != -1;i = ne[i])cout << w[i] <<endl;
    // cout << 0x3f3f3f3f <<endl;
    jks();

    cout << dist[2 * n];
    return 0;
}