url: https://www.luogu.com.cn/problem/P3110

tag:
USACO14DEC，最短路，bfs，USACO，2014

思路：
求三遍最短路，分别是正着求Bessie 和 Elsie 到每个点的最短路，和逆着求终点n到每个点的最短路，然后枚举看从哪个点开始一起走（Bessie 可以背着 Elsie 走）然后到终点的能量最小，更新ans。最后输出ans即可。

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int B, E, P, n, m;
int idx, e[N], ne[N], h[N], w[N];
int distB[N], distE[N], distP[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = 1;
    h[a] = idx ++;
}
void dijkstra(int s, int dist[])
{
    memset(st, 0, sizeof st);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});

    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(distE, 0x3f, sizeof distE);
    memset(distB, 0x3f, sizeof distB);
    memset(distP, 0x3f, sizeof distP);
    cin >> B >> E >> P >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dijkstra(1, distB);
    dijkstra(2, distE);
    dijkstra(n, distP);
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i ++)
    {
        ans = min(ans, B * distB[i] + E * distE[i] + P * distP[i]);
    }
    cout << ans;
    return 0;
}