奶牛派对-艾默生ups电源nx系列（30-200kva）

图 4.17 奶牛派对 本题两次运用 SPFA 算法求 短距离： (1) 以农场 X 为源点，各顶点的出边构成的邻接表，求源点到各农场的 短距离，该距离是 从各农场到农场 X 的 少时间； (2) 以农场 X 为源点，各顶点的入边作为出边，构成邻接表，求源点到各农场的 短距离， 该距离是从农场 X 返回各农场的 少时间。 将两个 少时间加起来，得到每头奶牛往返农场 X 的 少时间，本题要求的是这些 少时间 的 大值。 代码如下： #include <cstdio> #include <cstring> #define MAXN 101000 #define INT_MAX 2000000 struct NODE //邻接表结构 { int v; int w; NODE *next; }edge[MAXN], redge[MAXN], temp[MAXN * 2]; // edge 与 redge 分别为正向图和反向图 int pos = 0; int ecost[MAXN]; int N, M, W, src, Q[MAXN]; //用数组 Q 模拟队列 bool visited[MAXN]; //标志数组，记录节点是否已访问 //SPFA 算法，direction 表示方向，0 为正向，1 为反向 void SPFA( int direction ) { int h, t, u, i; NODE *ptr;