526互联

[USACO] Piggy Back

发布时间 2023-10-14 07:48:52作者: 南松的科技树

[USACO] Piggy Back

题目大概意思是一个无向图，Bessie 从 1 号仓库走到 n 号（每次花费 x）， Elsie 从 2 号仓库走到 n 号（每次花费 y），如果两个人走同一条路花费 z，求总花费最小。

跑三遍最短路,别得到 Bessie 从 1 号仓库出发的最短路,Elsie 从 2 号仓库出发的最短路,和从 n 出发到其他每个点的最短路。

在走到相遇点之前，两人一定走的是对应最短路才能减小花费

不难得出 \(ans = min(ans, x * d1[i] + y * d2[i] + z * d3[i])\)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

#define rint register int
#define endl '\n'

using std::cin;
using std::cout;

const int inf = 0x3f3f3f3f;
const int N = 1e6 + 5;
const int M = 4e6 + 5;

int n, m, s;
int idx, h[N], e[M], ne[M], d1[N], d2[N], d3[N];
bool v[N];
std::priority_queue<std::pair<int, int>> q;

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

void dijkstra(int s, int *dist)
{
    for (rint i = 1; i <= n; i++)
    {
        dist[i] = inf;
    }
    memset(v, 0, sizeof v);
    dist[s] = 0;
    q.push(std::make_pair(0, s));

    while (!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (v[x])
        {
            continue;
        }
        v[x] = 1;
        for (rint i = h[x]; i; i = ne[i])
        {
            int y = e[i];
            int z = 1;
            if (dist[y] > dist[x] + z)
            {
                dist[y] = dist[x] + z;
                q.push(std::make_pair(-dist[y], y));
            }
        }
    }
}

int x, y, z;

int main()
{
    cin >> x >> y >> z >> n >> m;

    for (rint i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    dijkstra(1, d1);
    dijkstra(2, d2);
    dijkstra(n, d3);

    int ans = inf;

    for (rint i = 1; i <= n; i++)
    {
        ans = std::min(ans, x * d1[i] + y * d2[i] + z * d3[i]);
    }

    cout << ans << endl;

    return 0;
}