ABC325 | E - Our clients, please wait a moment 题解

· · 题解

题解

最短路板子练习题。

观察到题目有一个性质：可以从公司汽车换乘火车，但不能反之。 也就是说我能在某个点选择换乘，换乘之前都是坐汽车，换乘后都是坐火车。

于是这题就很显然了。有 2 种解决方法：

第一种做法：正反跑两遍最短路。计算出从 1 出发，只坐汽车到每个点的最短距离 disa；计算从 n 出发，只坐火车到每个点的最短距离 disb。于是枚举每个点作为换乘点，取 disa+disb 的最小值即可。 即 ans=\sum_{i=1}^n \min(disa_i+disb_i)。

第二种做法：分层图。把只坐汽车和只坐火车分别建两个图，记为 a 图和 b 图。然后把 a 图的每个节点建立一条指向 b 图中对应的点的有向边，边权为 0。然后在这个图里跑一遍最短路即可。

第二种做法其实相对更优雅一点，因为只用跑一次最短路。

## $\text{Code:}

这里我用的第一种做法，最短路写的 dijkstra。

#include<bits/stdc++.h>
#define maxn 1050
#define maxm 500050 
#define endl '\n'
#define ll long long
using namespace std;

const ll llinf = 999999999999999;

int n, a, b, c; 
ll d[maxn][maxn];
ll disa[maxn], disb[maxn];
bool visa[maxn], visb[maxn];
priority_queue <pair<ll, int> > q;
ll ans = llinf;

void dija(int s)
{
    q.push(make_pair(0, s));
    disa[s] = 0;
    while(q.size())
    {
        int x = q.top().second; q.pop();
        visa[x] = true;
        for(int i = 1; i <= n; i ++)
        {
            if(visa[i]) continue;
            if(disa[x] + d[x][i] * a < disa[i])
            {
                disa[i] = disa[x] + d[x][i] * a;
                q.push(make_pair(-disa[i], i));
            }
        }
    }
}

void dijb(int s)
{
    q.push(make_pair(0, s));
    disb[s] = 0;
    while(q.size())
    {
        int x = q.top().second; q.pop();
        if(visb[x]) continue;
        visb[x] = true;
        for(int i = 1; i <= n; i ++)
        {
            if(disb[x] + d[x][i] * b + c < disb[i])
            {
                disb[i] = disb[x] + d[x][i] * b + c;
                q.push(make_pair(-disb[i], i));
            }
        }
    }
}

void run()
{
    cin >> n >> a >> b >> c;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> d[i][j];
    memset(disa, -llinf, sizeof(disa)); 
    memset(disb, -llinf, sizeof(disb)); 
    dija(1); dijb(n);
    for(int i = 1; i <= n; i ++)
        ans = min(disa[i] + disb[i], ans);
    cout << ans << endl;
}

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

    int t = 1;
//  cin >> t; 
    while(t --) run();

    return 0;
}