洛谷P3110 《[USACO14DEC]驮运Piggy Back》

十月 04, 2018 6559

披着蓝题的皮跑3遍SPFA的绿题

题目链接

题面

由于翻译缺失，暂不提供翻译，这里仅提供英文题面。

题目描述

Bessie and her sister Elsie graze in different fields during the day, and in the evening they both want to walk back to the barn to rest. Being clever bovines, they come up with a plan to minimize the total amount of energy they both spend while walking.

Bessie spends B units of energy when walking from a field to an adjacent field, and Elsie spends E units of energy when she walks to an adjacent field. However, if Bessie and Elsie are together in the same field, Bessie can carry Elsie on her shoulders and both can move to an adjacent field while spending only P units of energy (where P might be considerably less than B+E, the amount Bessie and Elsie would have spent individually walking to the adjacent field). If P is very small, the most energy-efficient solution may involve Bessie and Elsie traveling to a common meeting field, then traveling together piggyback for the rest of the journey to the barn. Of course, if P is large, it may still make the most sense for Bessie and Elsie to travel

separately. On a side note, Bessie and Elsie are both unhappy with the term “piggyback”, as they don’t see why the pigs on the farm should deserve all the credit for this remarkable form of

transportation.

Given B, E, and P, as well as the layout of the farm, please compute the minimum amount of energy required for Bessie and Elsie to reach the barn.

输入输出格式

INPUT: (file piggyback.in)

The first line of input contains the positive integers B, E, P, N, and M. All of these are at most 40,000. B, E, and P are described above. N is the number of fields in the farm (numbered 1..N, where N >= 3), and M is the number of connections between fields. Bessie and Elsie start in fields 1 and 2, respectively. The barn resides in field N.

The next M lines in the input each describe a connection between a pair of different fields, specified by the integer indices of the two fields. Connections are bi-directional. It is always possible to travel from field 1 to field N, and field 2 to field N, along a series of such connections.

OUTPUT: (file piggyback.out)

A single integer specifying the minimum amount of energy Bessie and

Elsie collectively need to spend to reach the barn. In the example

shown here, Bessie travels from 1 to 4 and Elsie travels from 2 to 3

to 4. Then, they travel together from 4 to 7 to 8.

输入样例

1
2
3
4
5
6
7
8
9
4 4 5 8 8 
1 4 
2 3 
3 4 
4 7 
2 5 
5 6 
6 8 
7 8

输出样例

1
22

解题思路

为什么这是蓝题 这应该是绿题啊~~

首先肯定是跑最短路

两只牛有这样两种选择：

  • 各自走回家
  • 走到任意一点之后 Bessie 背着 Elsie 回家

那么我们就跑3遍SPFA即可

  1. 以 Bessie 为起点（即1点）
  2. 以 Elsie 为起点（即2点）
  3. 以家为起点（即n点）

这里有个小技巧，不需要写3遍不同的SPFA，只需要把3个dis数组当做参数传进去即可

最后暴力枚举图中的所有点 i

如果设 (u,v) 为 u\rightarrow v 的最短路长度的话，

答案就是最小的 (1,i)+(2,i)+(n,i)

注意判断点不连通（距离为INF）的情况

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 4000000 + 10;
    const int MAXM = 4000000 + 10;
    
    const int INF = 0x3f3f3f3f;
    
    int b, e, p, n, m;
    int head[MAXN], disB[MAXN], disE[MAXN], disN[MAXN];
    bool inQueue[MAXN];
    int cnt;
    
    struct Edge {
        int prev, next, weight;
    } edge[MAXM];
    
    inline void addEdge(int prev, int next) {
        edge[++cnt].prev = prev;
        edge[cnt].next = head[next];
        head[next] = cnt;
        edge[cnt].weight = 1;
    }
    
    void SPFA(int dis[], int s) {
        //memset(dis, 0, sizeof(dis));
        For (i, 0, n) dis[i] = INF;
        dis[s] = 0;
        queue<int> q;
        q.push(s);
        inQueue[s] = true;
        while (!q.empty()) {
            int prev = q.front();
            q.pop();
            inQueue[prev] = false;
            for (int e = head[prev]; e; e = edge[e].next) {
                if (dis[edge[e].prev] > dis[prev] + edge[e].weight) {
                    dis[edge[e].prev] = dis[prev] + edge[e].weight;
                    if (!inQueue[edge[e].prev]) {
                        q.push(edge[e].prev);
                        inQueue[edge[e].prev] = true;
                    }
                }
            }
        }
    }
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
    #endif
    using namespace Solution;
    using namespace FastIO;
    b = getint();
    e = getint();
    p = getint();
    n = getint();
    m = getint();
    For (i, 1, m) {
        int prev, next;
        prev = getint();
        next = getint();
        addEdge(prev, next);
        addEdge(next, prev);
    }
    SPFA(disB, 1);
    SPFA(disE, 2);
    SPFA(disN, n);
    int ans = 2147482333;
    For (i, 1, n) {
        if (disN[1] == INF 
            || disN[2] == INF 
            || disB[i] == INF 
            || disE[i] == INF 
            || disN[i] == INF
        ) continue;
        ans = std::min(ans, b * disB[i] + e * disE[i] + p * disN[i]);
    }
    putint(ans, '\n');
    return 0;
}