解题思路
看到下面很多人都在说什么遇到了之后要不要背着走，其实根本不需要，同样的我也是跑了三遍$SPFA$，求出了以$1$为起点到个点的$dist$，和以$2$为起点到个点的$dist$，还有以$n$为起点到个点的$dist$。
之后直接枚举两头牛在哪里相遇，相遇之后一起背着走的路程乘以$p+$相遇之前$B$走的距离乘以$b+$相遇之前$E$走的距离乘以$e$，去一个最小的这样的值就是答案。
关于为什么不需要分类讨论，因为你把每个点都枚举了一遍，即使存在$p>b+e$的情况，那这种情况就等价于两头奶牛在$n$点相遇。
附上代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int maxn = 8e4+
3, INF =
2147483647;
int b, e, p, n, m, fir[maxn], nxt[maxn], u[maxn], v[maxn], cnt;
int dist_n[maxn], dist_1[maxn], dist_2[maxn], w[maxn], Ans =
INF;
bool vis[maxn];
inline int read() {
int x =
0, f =
1;
char c;
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1; c =
getchar();}
while (c <=
'9' && c >=
'0') {x = x*
10 + c-
'0'; c =
getchar();}
return x *
f;
}
inline void addedge(
int x,
int y,
int z) {
nxt[++cnt] =
fir[x];
fir[x] =
cnt;
u[cnt] = x, v[cnt] = y, w[cnt] =
z;
}
inline void SPFA(
int s,
int *
dist) {
std::queue<
int>
Q;
std::memset(vis, 0,
sizeof(vis));
std::fill(dist+
1, dist+
1+
n, INF);
vis[s] =
1, dist[s] =
0;
Q.push(s);
int x, k;
while (!
Q.empty()) {
x =
Q.front(), Q.pop();
int k =
fir[x];
while (k != -
1) {
if(dist[v[k]] > dist[u[k]] +
w[k]) {
dist[v[k]] = dist[u[k]] +
w[k];
if(!
vis[v[k]]) Q.push(v[k]);
}
k =
nxt[k];
}
vis[x] =
0;
}
}
int main() {
b = read(), e = read(), p = read(), n = read(), m =
read();
std::memset(fir, -
1,
sizeof(fir));
int x, y, z =
1;
for(register
int i=
1; i<=m; i++
) {
x = read(), y =
read();
addedge(x, y, z), addedge(y, x, z);
}
SPFA(1, dist_1), SPFA(
2, dist_2), SPFA(n, dist_n);
for(
int i=
1; i<=n; i++
)
Ans = std::min(Ans, dist_1[i] * b + dist_2[i] * e + dist_n[i] *
p);
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9494330.html
相关资源：数据结构—成绩单生成器
