一 原问题链接

Silver Cow Party - POJ 3268 - Virtual Judge

https://vjudge.net/problem/POJ-3268

二 输入和输出

1 输入

第1行包含3个整数N、M、X。在第2~M+1行中，第 i+1 描述到了 i，有三个整数：Ai、Bi和Ti，表示从 Ai 农场到 Bi 农场需要 Ti 时间。

2 输出

单行输出母牛必须花费的时间的最大值。

三 输入和输出样例

1 输入样例

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

2 输出样例

10

四 分析

根据输入样例，共有4个农场、8条路，聚会地点在2号农场。母牛从4号农场出发，走一个回路 4-2-1-3-4 ，共计 10 个时间，该时间是所有母牛中来回时间最长的，如下图所示。

五 算法设计

因为母牛来回走的都是最短路径，所以先求从出发点到聚会点来回的最短路径之和，然后秋最大值即可。

1 从 i 号农场到聚会地点 X，相对于在反向图中从 X 到 i。

2 从聚会地点 X 返回 i 号农场，相对于在正向图中从 X 到 i。、

3 创建正向图和反向图，都把 X 作为源点，分别调用 SPFA 算法求正向图、反向图中源点到其他各个点最短时间 dis[i] 和 rdis[i],求最大和值。

六 算法实现

package graph.poj3268;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.atomic.AtomicInteger;

public class Poj3268 {
    static final int maxn = 10005;
    static final int inf = 0x3f3f3f3f;
    static int n;
    static int m;
    static int x;
    static AtomicInteger cnt = new AtomicInteger(0);
    static AtomicInteger rcnt = new AtomicInteger(0);
    static node e[] = new node[maxn];
    static node re[] = new node[maxn];
    static int head[] = new int[maxn];
    static int rhead[] = new int[maxn];
    static int dis[] = new int[maxn];
    static int rdis[] = new int[maxn];
    // 标记是否在队列中
    static boolean vis[] = new boolean[maxn];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
        for (int i = 0; i < re.length; i++) {
            re[i] = new node();
        }
    }

    static void add(node e[], int head[], int u, int v, int w, AtomicInteger cnt) {
        e[cnt.get()].to = v;
        e[cnt.get()].next = head[u];
        e[cnt.get()].w = w;
        head[u] = cnt.getAndIncrement();
    }

    static void spfa(node e[], int head[], int u, int dis[]) {
        Queue<Integer> q = new LinkedList<>();
        vis = new boolean[maxn];
        for (int i = 0; i < dis.length; i++) {
            dis[i] = inf;
        }
        vis[u] = true;
        dis[u] = 0;
        q.add(u);
        while (!q.isEmpty()) {
            int x = q.peek();
            q.poll();
            vis[x] = false;
            for (int i = head[x]; i >= 0; i = e[i].next) {
                if (dis[e[i].to] > dis[x] + e[i].w) {
                    dis[e[i].to] = dis[x] + e[i].w;
                    if (!vis[e[i].to]) {
                        vis[e[i].to] = true;
                        q.add(e[i].to);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        x = scanner.nextInt();

        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }
        for (int i = 0; i < rhead.length; i++) {
            rhead[i] = -1;
        }
        int u, v, w;
        for (int i = 1; i <= m; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            w = scanner.nextInt();
            add(e, head, u, v, w, cnt);
            add(re, rhead, v, u, w, rcnt); // 反向图
        }
        spfa(e, head, x, dis);
        spfa(re, rhead, x, rdis);
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans = Math.max(ans, dis[i] + rdis[i]);
        System.out.println(ans);
    }
}

class node {
    int to;
    int w;
    int next;
}

七 测试

绿色为输入，白色为输出。

八 参考

Java：通过引用传递int的最佳方法