USACO 2014 Dec Silver 1.Piggyback

2015.03.04 11:28 Wed| 12 visits oi_2015| 2015_刷题日常| Text

Solution

分别计算从 1、2、N 三点出发的单源最短路。然后枚举两人的会合点 i ,更新答案。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 40005
#define M 80005

int b, e, p, n, m, head[N], d[3][N];
long long ans = 0x3f3f3f3f3f3f3f3f;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void bfs(int s, int d[])
{
    queue<int> q;
    q.push(s); d[s] = 0;
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].to != s && !d[edge[i].to])
                d[edge[i].to] = d[x] + 1, q.push(edge[i].to);
    }
}

int main()
{
    cin >> b >> e >> p >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    bfs(1, d[0]); bfs(2, d[1]), bfs(n, d[2]);
    for (int i = 1; i <= n; ++i)
        ans = min(ans, 1ll * b * d[0][i] + 1ll * e * d[1][i] + 1ll * p * d[2][i]);
    cout << ans << endl;
}