挑战程序竞赛系列(11):2.5最短路径

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/73350943

挑战程序竞赛系列(11):2.5最短路径

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

AOJ 0189: Convenient Location

思路: 更新任意两点之间的最短距离,采用松弛法,现成的算法有Floyd-Warshall算法,代码如下:

public class Main {

    static final int MAX_LOC = 10;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        String[] words;

        while ((line = br.readLine()) != null && !line.isEmpty()) {

            int n = parseInt(line);
            if (n == 0) break;

            //init
            long[][] g = new long[MAX_LOC][MAX_LOC];
            int N = 0;

            for (int i = 0; i < g.length; i++) {
                for (int j = 0; j < g[i].length; j++) {
                    if (i != j) g[i][j] = Integer.MAX_VALUE;
                }
            }
            for (int i = 0; i < n; i++) {
                words = br.readLine().split(" ");
                int x, y, d;
                x = parseInt(words[0]);
                y = parseInt(words[1]);
                d = parseInt(words[2]);
                N = Math.max(N, Math.max(x, y));
                g[y][x] = g[x][y] = d;
            }

            //solve
            for (int k = 0; k <= N; k++) {
                for (int i = 0; i <= N; i++) {
                    for (int j = 0; j <= N; j++) {
                        g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                    }
                }
            }

            int pos = Integer.MAX_VALUE;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i <= N; i++) {
                int tmp = 0;
                for (int j = 0; j <= N; j++) {
                    tmp += g[i][j];
                }
                if (tmp < min) {
                    pos = i;
                    min = tmp;
                }
            }

            System.out.println(pos + " " + min);

        }
    }
}

POJ 2139: Six Degrees of Cowvin Bacon

和第一题一个思路,没什么好说的,代码如下:

static int INF = 1 << 29;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] g = new int[N][N];

        for (int i = 0; i < N; ++i) Arrays.fill(g[i],INF);
        for (int i = 0; i < N; ++i) g[i][i] = 0;

        for (int i = 0; i < M; ++i){
            int n = in.nextInt();
            int[] x = new int[n];
            for (int j = 0; j < n; ++j){
                x[j] = in.nextInt();
                x[j]--;
            }
            for (int k = 0; k < n; ++k){
                for (int l = k + 1; l < n; ++l){
                    g[x[k]][x[l]] = g[x[l]][x[k]] = 1;
                }
            }
        }

        for (int i = 0; i < N; ++i){
            for (int j = 0; j < N; ++j){
                for (int k = 0; k < N; ++k){
                    g[j][k] = Math.min(g[j][k],g[j][i] + g[i][k]);
                }
            }
        }

        int ans = INF;
        for (int i = 0; i < N; ++i){
            int sum = 0;
            for (int j = 0; j < N; ++j){
                sum += g[i][j];
            }
            ans = Math.min(ans, sum);
        }

        System.out.println(100 * ans / (N - 1));
    }

POJ 3268: Sliver Cow Party

求从某个顶点出发,到达目标顶点X之后再回到原地的所有最短路径中的最大值。

思路:(warShallFloyd算法) 它能求任意两点之间的最短距离,时间复杂度为O(n3)O(n^3)。代码如下:

static int INF = 1 << 29;
    static int[][] g;
    static int N;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();

        int M = in.nextInt();
        int X = in.nextInt();
        g = new int[N][N];
        d = new int[N][N];
        for (int i = 0; i < N; ++i) Arrays.fill(g[i], INF);
        for (int i = 0; i < N; ++i) g[i][i] = 0;

        for (int i = 0; i < M; ++i){
            int f = in.nextInt();
            int t = in.nextInt();
            f--;
            t--;
            int c = in.nextInt();
            g[f][t] = c;
        }

        warshallFloyd();

        int max = 0;
        for (int i = 0; i < N; ++i){
            if (i == X) continue;
            max = Math.max(max, g[i][X] + g[X][i]);
        }
        System.out.println(max);
    }
    private static void warshallFloyd(){
        for (int i = 0; i < N; ++i){
            for (int j = 0; j < N; ++j){
                for (int k = 0; k < N; ++k){
                    g[j][k] = Math.min(g[j][k], g[j][i] + g[i][k]);
                }
            }
        }
    }

TLE了,顶点数1000,所以需要执行100031000^3次,自然TLE,所以必须优化,采用DIJKSTRA算法,因为此题已经表明不存在负环,所以可以使用DIJKSTRA来计算任意两点之间的距离。

为什么有负环dijkstra算法就不适用了?其次,dijkstra算法为什么就比warshallFloyd算法快?之前困扰了我很久,今天能够解释了。关键问题在于负边是否存在。

Dijkstra:假设所有边都为正,不存在负环。

为什么需要这假设?这跟改进算法时间复杂度有关,在warshallFloyd算法中,每一轮操作都需要访问每个顶点,即时这个顶点已经被更新为最短路径,所以DIJKSTRA的一个优化思路是:

既然优先顶点已经知道了到源点s的最短距离是多少,它们在未来,到达该顶点的路径不需要再比较。

问题来了,该如何得知这个顶点已经是最短路径上的一个顶点了?DIJKSTRA把整个顶点集划分为【最短路径顶点集】和【未确定顶点集】,目标就是在每一轮松弛操作后,能够得到当前一个最短路径上的顶点。

有了这顶点有什么作用呢?因为源点到该顶点的路径一定是最短的,所以从该顶点出发连接未确定顶点集的路径中,必然会出现一条最短路径,指向一个新的顶点。

最重要的是,我们没必要更新其他顶点的连接边,因为它们还不是最短路径,更新无意义。而是仅更新从该顶点出发的所有邻接的顶点。

此处体现了算法的一个优化(更新了相邻顶点的边,而不是每轮所有边)。

证明:

源点到该顶点的路径一定是最短的,所以从该顶点出发连接未确定顶点集的路径中,必然会出现一条最短路径,指向一个新的顶点。

上述这结论需要证明一下,DIJKSTAR最重要的假设是不存在负边,还有一个重要的事实,不管松弛与否,更新必然导致d[i]递减,d[i]表示源点s到i的路径,所以d[i]是不可能递增的。

好了,现在经过第k轮,得到了d[i]是源点s到i的【最短路径】,我们选择方法是:

从前一轮最短路径的某个顶点出发,更新所有与之相连的顶点j,选择【未确定顶点集】中的d[j]最小的顶点为新的最短路径顶点。

注意是最小!这样就保证了更新的正确性,所以d[i]对我们来说,是所有其他d[j]的最小值,那么是否存在其他路径使得到d[i]的距离比现在还小呢?

没有,因为其他顶点d[j] > d[i],而任何从顶点j到顶点i的连接边都是正值,不可能有比d[i]小的路径存在,所以d[i]已经是最短路径中的一个顶点了。那么由此更新它的每一条边必然是安全的。(用到了最重要的不存在负边的假设)

代码如下:

static int INF = 1 << 29;
    static int[][] g;
    static int[][] d;
    static int N;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();

        int M = in.nextInt();
        int X = in.nextInt();
        g = new int[N][N];
        d = new int[N][N];
        for (int i = 0; i < N; ++i) Arrays.fill(g[i], INF);
        for (int i = 0; i < N; ++i) g[i][i] = 0;

        for (int i = 0; i < M; ++i){
            int f = in.nextInt();
            int t = in.nextInt();
            f--;
            t--;
            int c = in.nextInt();
            g[f][t] = c;
        }

        for (int i = 0; i < N; ++i){
            //initial
            Arrays.fill(d[i], INF);
            d[i][i] = 0;
            dijkstra(i);
        }

        int max = 0;
        for (int i = 0; i < N; ++i){
            if (i == X) continue;
            max = Math.max(max, d[i][X] + d[X][i]);
        }
        System.out.println(max);
    }

    private static void dijkstra(int s){
        int V = N;
        boolean[] used = new boolean[V];
        while (true){
            int v = -1;
            for (int i = 0; i < V; ++i){
                if (!used[i] && (v == -1 || d[s][i] < d[s][v])) v = i;
            }
            if (v == -1) break;
            used[v] = true;
            for (int i = 0; i < V; ++i){
                d[s][i] = Math.min(d[s][i],d[s][v] + g[v][i]);
            }
        }
    }

求任意两点之间的距离,需要对djkstra做些改变,但依旧TLE了,呵呵,这是因为算法复杂度还是为O(n3)O(n^3),DIJKSTRA算法的复杂度为O(n2)O(n^2),这和我们使用邻接矩阵有关系,我们在更新时,并不知道谁和谁到底是相连的,所以还是更新每条边。

所以与其这样,我们不如优化我们的存储图的结构,邻接表是很好的选择,对于每个顶点,都知道与它相连的顶点的是谁,起码比上述做法要快很多。

还有一点,每次求最小值需要O(n)O(n)?在动态结构下,每次求最小,我们有一种O(logn)O(\log n)的结构,没错,就是堆,所以这才是DIJKSTRA算法快的真正原因,最小值的维护用优先队列就可以了。而之所以能用最小值,前文已经叙述过了。

代码如下:

static int INF = 1 << 29;
    static int[][] d;
    static List<Edge>[] graph;
    static int N;

    static class Edge{
        int from;
        int to;
        int cost;

        @Override
        public String toString() {
            return from + "->" + to + " ,cost: " + cost;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();

        int M = in.nextInt();
        int X = in.nextInt();
        graph = new ArrayList[N];

        d = new int[N][N];
        for (int i = 0; i < N; ++i) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; ++i){
            int f = in.nextInt();
            int t = in.nextInt();
            f--;
            t--;
            int c = in.nextInt();
            Edge e = new Edge();
            e.from = f;
            e.to = t;
            e.cost = c;
            graph[e.from].add(e);
        }

        for (int i = 0; i < N; ++i){
            //initial
            Arrays.fill(d[i], INF);
            d[i][i] = 0;
            dijkstra(i);
        }

        int max = 0;
        for (int i = 0; i < N; ++i){
            if (i == X) continue;
            max = Math.max(max, d[i][X] + d[X][i]);
        }
        System.out.println(max);
    }

    private static void dijkstra(int s){
        int V = N;
        IndexMinPQ<Integer> pq = new IndexMinPQ<>(V);
        pq.insert(s, d[s][s]);
        while (!pq.isEmpty()){
            int v = pq.delMin();
            for (Edge e : graph[v]){
                int from = e.from;
                int to = e.to;
                int cost = e.cost;
                if (d[s][from] + cost < d[s][to]){
                    d[s][to] = d[s][from] + cost;
                    if (pq.contains(to)) pq.decreaseKey(to, d[s][to]);
                    else pq.insert(to, d[s][to]);
                }
            }
        }
    }

这里的IndexMinPQ是一种特殊的优先队列,可以支持索引查找元素以及在更新元素大小后,自动上沉下浮,此处就不在阐述了。

唉,这道题还可以更快,可以利用无向图的性质来做这件事,这样两次dijkstra就完事了,说下思路吧。

  • 从X到每个顶点的最短距离,一次dijkstra(X)即可。
  • 如果是无向图,任何顶点到X的最短距离,一定也是X到任何顶点的最短距离,所以此图可以来个反向,这样相当于求无向图中的顶点X到任何顶点的最短距离,再来一次dijkstra(X),OK!

AOJ 2249: Road Construction

给一版完整的实现,这道题是求最短路径相同的那些边的cost最小,所以先用dijkstra求一次最短路径,接着找到所有最短路径的边,选择cost最小的边即可。

刚开始尝试了邻接矩阵的Dijkstra,结果MLE了,呵呵哒。只不过这种Dijkstra算法速度和Floyd算法差不多,还不如用堆+邻接表。

完整代码如下:

public class SolutionDay16_A2249 {

    static class Edge{
        int from;
        int to;
        int dist;
        int cost;

        @Override
        public String toString() {
            return "{"+from + "->" + to + ", dist: " + dist + "}";
        }
    }

    static int INF = 1 << 29;
    static List<Edge>[] graph;
    static int[] dist;
    static int N;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (true){
            N = in.nextInt();
            int M = in.nextInt();
            if (N == 0 && M == 0) break;
            graph = new ArrayList[N];
            for (int i = 0; i < N; ++i) graph[i] = new ArrayList<>();

            for (int i = 0; i < M; ++i){
                int f = in.nextInt();
                int t = in.nextInt();
                f--;
                t--;
                int dist = in.nextInt();
                int cost = in.nextInt();

                Edge edge = new Edge();
                edge.from = f;
                edge.to = t;
                edge.cost = cost;
                edge.dist = dist;
                graph[edge.from].add(edge);

                edge = new Edge();
                edge.from = t;
                edge.to = f;
                edge.cost = cost;
                edge.dist = dist;
                graph[edge.from].add(edge);
            }

            dijkstra(0);
            long sum = 0;
            for (int i = 1; i < N; ++i){
                int min = INF;
                for (Edge e : graph[i]){
                    if (dist[i] == dist[e.to] + e.dist && e.cost < min){
                        min = e.cost;
                    }
                }
                sum += min;
            }
            System.out.println(sum);
        }
    }

    private static void dijkstra(int s){
        dist = new int[N];
        Arrays.fill(dist,INF);
        dist[s] = 0;
        IndexMinPQ<Integer> pq = new IndexMinPQ<>(N);
        pq.insert(s, dist[s]);
        while (!pq.isEmpty()){
            int v = pq.delMin();
            for (Edge e : graph[v]){
                if (dist[e.from] + e.dist < dist[e.to]){
                    dist[e.to] = dist[e.from] + e.dist;
                    if (pq.contains(e.to)) pq.decreaseKey(e.to, dist[e.to]);
                    else pq.insert(e.to, dist[e.to]);
                }
            }
        }
    }

    static class Scanner {

        private BufferedReader br;
        private StringTokenizer tok;

        public Scanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            getLine();
        }

        private void getLine() throws IOException {
            while (tok == null || !tok.hasMoreTokens()) {
                tok = new StringTokenizer(br.readLine());
            }
        }

        private boolean hasNext() {
            return tok.hasMoreTokens();
        }

        public String next() throws IOException {
            if (hasNext()) {
                return tok.nextToken();
            } else {
                getLine();
                return tok.nextToken();
            }
        }

        public int nextInt() throws IOException {
            if (hasNext()) {
                return Integer.parseInt(tok.nextToken());
            } else {
                getLine();
                return Integer.parseInt(tok.nextToken());
            }
        }

        public long nextLong() throws IOException {
            if (hasNext()) {
                return Long.parseLong(tok.nextToken());
            } else {
                getLine();
                return Long.parseLong(tok.nextToken());
            }
        }

        public double nextDouble() throws IOException {
            if (hasNext()) {
                return Double.parseDouble(tok.nextToken());
            } else {
                getLine();
                return Double.parseDouble(tok.nextToken());
            }
        }
    }

    static class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
        private int maxN;        // maximum number of elements on PQ
        private int n;           // number of elements on PQ
        private int[] pq;        // binary heap using 1-based indexing
        private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
        private Key[] keys;      // keys[i] = priority of i

        /**
         * Initializes an empty indexed priority queue with indices between {@code 0}
         * and {@code maxN - 1}.
         * @param  maxN the keys on this priority queue are index from {@code 0}
         *         {@code maxN - 1}
         * @throws IllegalArgumentException if {@code maxN < 0}
         */
        @SuppressWarnings("unchecked")
        public IndexMinPQ(int maxN) {
            if (maxN < 0) throw new IllegalArgumentException();
            this.maxN = maxN;
            n = 0;
            keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
            pq   = new int[maxN + 1];
            qp   = new int[maxN + 1];                   // make this of length maxN??
            for (int i = 0; i <= maxN; i++)
                qp[i] = -1;
        }

        /**
         * Returns true if this priority queue is empty.
         *
         * @return {@code true} if this priority queue is empty;
         *         {@code false} otherwise
         */
        public boolean isEmpty() {
            return n == 0;
        }

        /**
         * Is {@code i} an index on this priority queue?
         *
         * @param  i an index
         * @return {@code true} if {@code i} is an index on this priority queue;
         *         {@code false} otherwise
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         */
        public boolean contains(int i) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            return qp[i] != -1;
        }

        /**
         * Returns the number of keys on this priority queue.
         *
         * @return the number of keys on this priority queue
         */
        public int size() {
            return n;
        }

        /**
         * Associates key with index {@code i}.
         *
         * @param  i an index
         * @param  key the key to associate with index {@code i}
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @throws IllegalArgumentException if there already is an item associated
         *         with index {@code i}
         */
        public void insert(int i, Key key) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
            n++;
            qp[i] = n;
            pq[n] = i;
            keys[i] = key;
            swim(n);
        }

        /**
         * Returns an index associated with a minimum key.
         *
         * @return an index associated with a minimum key
         * @throws NoSuchElementException if this priority queue is empty
         */
        public int minIndex() {
            if (n == 0) throw new NoSuchElementException("Priority queue underflow");
            return pq[1];
        }

        /**
         * Returns a minimum key.
         *
         * @return a minimum key
         * @throws NoSuchElementException if this priority queue is empty
         */
        public Key minKey() {
            if (n == 0) throw new NoSuchElementException("Priority queue underflow");
            return keys[pq[1]];
        }

        /**
         * Removes a minimum key and returns its associated index.
         * @return an index associated with a minimum key
         * @throws NoSuchElementException if this priority queue is empty
         */
        public int delMin() {
            if (n == 0) throw new NoSuchElementException("Priority queue underflow");
            int min = pq[1];
            exch(1, n--);
            sink(1);
            assert min == pq[n+1];
            qp[min] = -1;        // delete
            keys[min] = null;    // to help with garbage collection
            pq[n+1] = -1;        // not needed
            return min;
        }

        /**
         * Returns the key associated with index {@code i}.
         *
         * @param  i the index of the key to return
         * @return the key associated with index {@code i}
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @throws NoSuchElementException no key is associated with index {@code i}
         */
        public Key keyOf(int i) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            else return keys[i];
        }

        /**
         * Change the key associated with index {@code i} to the specified value.
         *
         * @param  i the index of the key to change
         * @param  key change the key associated with index {@code i} to this key
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @throws NoSuchElementException no key is associated with index {@code i}
         */
        public void changeKey(int i, Key key) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            keys[i] = key;
            swim(qp[i]);
            sink(qp[i]);
        }

        /**
         * Change the key associated with index {@code i} to the specified value.
         *
         * @param  i the index of the key to change
         * @param  key change the key associated with index {@code i} to this key
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @deprecated Replaced by {@code changeKey(int, Key)}.
         */
        @Deprecated
        public void change(int i, Key key) {
            changeKey(i, key);
        }

        /**
         * Decrease the key associated with index {@code i} to the specified value.
         *
         * @param  i the index of the key to decrease
         * @param  key decrease the key associated with index {@code i} to this key
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @throws IllegalArgumentException if {@code key >= keyOf(i)}
         * @throws NoSuchElementException no key is associated with index {@code i}
         */
        public void decreaseKey(int i, Key key) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            if (keys[i].compareTo(key) <= 0)
                throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
            keys[i] = key;
            swim(qp[i]);
        }

        /**
         * Increase the key associated with index {@code i} to the specified value.
         *
         * @param  i the index of the key to increase
         * @param  key increase the key associated with index {@code i} to this key
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @throws IllegalArgumentException if {@code key <= keyOf(i)}
         * @throws NoSuchElementException no key is associated with index {@code i}
         */
        public void increaseKey(int i, Key key) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            if (keys[i].compareTo(key) >= 0)
                throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
            keys[i] = key;
            sink(qp[i]);
        }

        /**
         * Remove the key associated with index {@code i}.
         *
         * @param  i the index of the key to remove
         * @throws IndexOutOfBoundsException unless {@code 0 <= i < maxN}
         * @throws NoSuchElementException no key is associated with index {@code i}
         */
        public void delete(int i) {
            if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            int index = qp[i];
            exch(index, n--);
            swim(index);
            sink(index);
            keys[i] = null;
            qp[i] = -1;
        }


       /***************************************************************************
        * General helper functions.
        ***************************************************************************/
        private boolean greater(int i, int j) {
            return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
        }

        private void exch(int i, int j) {
            int swap = pq[i];
            pq[i] = pq[j];
            pq[j] = swap;
            qp[pq[i]] = i;
            qp[pq[j]] = j;
        }


       /***************************************************************************
        * Heap helper functions.
        ***************************************************************************/
        private void swim(int k) {
            while (k > 1 && greater(k/2, k)) {
                exch(k, k/2);
                k = k/2;
            }
        }

        private void sink(int k) {
            while (2*k <= n) {
                int j = 2*k;
                if (j < n && greater(j, j+1)) j++;
                if (!greater(k, j)) break;
                exch(k, j);
                k = j;
            }
        }


       /***************************************************************************
        * Iterators.
        ***************************************************************************/

        /**
         * Returns an iterator that iterates over the keys on the
         * priority queue in ascending order.
         * The iterator doesn't implement {@code remove()} since it's optional.
         *
         * @return an iterator that iterates over the keys in ascending order
         */
        public Iterator<Integer> iterator() { return new HeapIterator(); }

        private class HeapIterator implements Iterator<Integer> {
            // create a new pq
            private IndexMinPQ<Key> copy;

            // add all elements to copy of heap
            // takes linear time since already in heap order so no keys move
            public HeapIterator() {
                copy = new IndexMinPQ<Key>(pq.length - 1);
                for (int i = 1; i <= n; i++)
                    copy.insert(pq[i], keys[pq[i]]);
            }

            public boolean hasNext()  { return !copy.isEmpty();                     }
            public void remove()      { throw new UnsupportedOperationException();  }

            public Integer next() {
                if (!hasNext()) throw new NoSuchElementException();
                return copy.delMin();
            }
        }
    }

}

勉强过了,速度还算可以。当然,我们完全可以借助Java自带的priorityQueue来实现,也非常容易理解,虽然会有重复id的结点,但这些顶点早就已经更新到了最小值,所以把它们poll出来后,不会再有新的元素push进去,利用这一点就无需在push的时候进行元素的上沉下浮。

代码如下:

static class Edge{
        int from;
        int to;
        int dist;
        int cost;

        @Override
        public String toString() {
            return "{"+from + "->" + to + ", dist: " + dist + "}";
        }
    }

    static int INF = 1 << 29;
    static List<Edge>[] graph;
    static int[] dist;
    static int N;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (true){
            N = in.nextInt();
            int M = in.nextInt();
            if (N == 0 && M == 0) break;
            graph = new ArrayList[N];
            for (int i = 0; i < N; ++i) graph[i] = new ArrayList<>();

            for (int i = 0; i < M; ++i){
                int f = in.nextInt();
                int t = in.nextInt();
                f--;
                t--;
                int dist = in.nextInt();
                int cost = in.nextInt();

                Edge edge = new Edge();
                edge.from = f;
                edge.to = t;
                edge.cost = cost;
                edge.dist = dist;
                graph[edge.from].add(edge);

                edge = new Edge();
                edge.from = t;
                edge.to = f;
                edge.cost = cost;
                edge.dist = dist;
                graph[edge.from].add(edge);
            }

            dijkstra(0);
            long sum = 0;
            for (int i = 1; i < N; ++i){
                int min = INF;
                for (Edge e : graph[i]){
                    if (dist[i] == dist[e.to] + e.dist && e.cost < min){
                        min = e.cost;
                    }
                }
                sum += min;
            }
            System.out.println(sum);
        }
    }

    static class Node implements Comparable<Node>{
        int id;
        int dist;
        public Node(int id, int dist){
            this.id = id;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

    private static void dijkstra(int s){
        dist = new int[N];
        Arrays.fill(dist,INF);
        dist[s] = 0;
        Queue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(s,dist[s]));
        while (!pq.isEmpty()){
            int v = pq.poll().id;
            for (Edge e : graph[v]){
                if (e.dist + dist[e.from] < dist[e.to]){
                    dist[e.to] = e.dist + dist[e.from];
                    pq.offer(new Node(e.to, dist[e.to]));
                }
            }
        }
    }

AOJ 2200: Mr. Rito Post Office

一道DP题,翻译可以参看博文AOJ 2200 Mr. Rito Post Office 题解 《挑战程序设计竞赛》,这道题目很有趣,分为水路和陆地,两种不同的状态,而且只有一艘船。

问题简化,首先,一定是按照顺寻每个地点进行寄快递,所以如果没有水路的话,可以直接求出任意两点之间的最短距离,每寄送一次,就把路径加上。

所以第一步一定是把两点间的最短路径分别求出来。(水路和陆地)

但问题来了,当遇到水路和陆地同时存在的情况?快递员就头大了,到底选择哪种方式去寄送快呢?如果就从局部来看,可以尝试贪心,每当进入一个城市后,如果当前城市有船,就尝试走水路和陆地,谁小,就取谁。而如果当前城市没船,则没有选择,直接走陆地。

我试着用这种方法去做,但发现答案并不对,这只能说明局部最优解不能推得整体最优。

既然这样,该dp就要复杂了,不是两个状态(有船or没船),而是在当前城市下,我的船在哪个城市。

所以我们有:

dp[i][j] 表示快递分送到第i个城市时,小船在城市j的最短路径。

这种多状态就好比,小船有了好多个虚拟分身,遍布在各大城市,的确高明。

现在假定有了dp[i-1][k]这样一个状态,如何更新到dp[i][j]

很简单,两种情况:
a. 小船的位置k == j,说明小船不需要移动,直接走陆地。
b. 小船的位置k != j,说明现在小船在其它城市,所以必须从i-1出发到城市k,在开船到j,把船停到j,再从陆地出发到i。

最后,求小船在不同位置时,状态i下的最小值即可。

代码如下:

static int[][] water;
    static int[][] land;
    static int N;
    static int INF = 1 << 28;
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (true){
            N = in.nextInt();
            int M = in.nextInt();
            if (N == 0 && M == 0) break;

            water = new int[N][N];
            land = new int[N][N];

            for (int i = 0; i < N; ++i){
                Arrays.fill(water[i], INF);
                Arrays.fill(land[i],INF);
                water[i][i] = 0;
                land[i][i] = 0;
            }

            for (int i = 0; i < M; ++i){
                int from = in.nextInt();
                int to = in.nextInt();
                from--;
                to--;

                int cost = in.nextInt();
                String mark = in.next();
                if (mark.equals("S")){
                    water[from][to] = water[to][from] = cost;
                }
                else{
                    land[from][to] = land[to][from] = cost;
                }
            }

            int C = in.nextInt();
            int[] city = new int[C];
            for (int i = 0; i < C; ++i){
                city[i] = in.nextInt() - 1;
            }

            warshallFloyd();

            int[][] dp = new int[C][N];
            for (int i = 0; i < C; ++i) Arrays.fill(dp[i], INF);
            for (int i = 0; i < N; ++i){
                dp[0][i] = land[city[0]][i] + water[i][city[0]];
            }

            for (int i = 1; i < C; ++i){
                for (int j = 0; j < N; ++j){
                    for (int k = 0; k < N; ++k){
                        if (j != k){
                            dp[i][k] = Math.min(dp[i][k], dp[i-1][j] + land[city[i-1]][j] + water[j][k] + land[k][city[i]]);
                        }
                        else{
                            dp[i][k] = Math.min(dp[i][k], dp[i-1][j] + land[city[i-1]][city[i]]);
                        }
                    }
                }
            }

            int min = INF;
            for (int i = 0; i < N; ++i){
                min = Math.min(min, dp[C-1][i]);
            }

            System.out.println(min);
        }
    }

    private static void warshallFloyd(){ 
        for (int i = 0; i < N; ++i){
            for (int j = 0; j < N; ++j){
                for (int k = 0; k < N; ++k){
                    water[j][k] = Math.min(water[j][k], water[j][i] + water[i][k]);
                    land[j][k] = Math.min(land[j][k], land[j][i] + land[i][k]);
                }
            }
        }
    }

如果能够联想到动规,这问题不难解决,但为什么就是动规呢?就从这道题来看,因为小船的位置无法根据当前状态【准确的】转移到下一状态,与其这样,我们不如让小船在各个位置都发生,所谓的多状态。这就好比小船的分身,虽然现实中并不是在一个阶段同时出现,但在问题求解过程中,我们可以假设小船在一个阶段中有多个状态,而走到最后一个状态时,再把所有小船消灭掉,留下一个最优的。孙悟空一吹猴毛,是为了打架,最后不还是要回归真身?有趣。

POJ 3259: Wormholes

有趣的虫洞,时间倒流?其实就是一个负环检测问题。负环检测,用到了Bellman算法,核心思想是说,在第V轮,若还在更新的话,说明检测到了负环。(这是一个充分必要条件,要证明还是比较麻烦。)

简单来说,一条简单最短路径(无0环),若有V个顶点,必然有V-1条边,所以更新V-1次,该路径就不会再有变化了,第一次给了源点d[s] = 0。这是最直观帮助我理解负环检测的算法,正确性还需要再探讨。

代码如下:

static class Edge{
        int from;
        int to;
        int cost;

        public String toString(){
            return from + "->" + to + " (" + cost + ")";
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int F = in.nextInt();
        while (F-- != 0){
            int V = in.nextInt();
            int p = in.nextInt();
            int w = in.nextInt();
            Edge[] edges = new Edge[2 * p + w];
            int E = 0;
            for (int i = 0; i < p; ++i){
                int from = in.nextInt();
                int to = in.nextInt();
                int cost = in.nextInt();
                from--;
                to--;

                Edge edge = new Edge();
                edge.from = from;
                edge.to = to;
                edge.cost = cost;
                edges[E++] = edge;

                edge = new Edge();
                edge.from = to;
                edge.to = from;
                edge.cost = cost;
                edges[E++] = edge;
            }

            for (int i = 0; i < w; ++i){
                int from = in.nextInt();
                int to = in.nextInt();
                int cost = in.nextInt();
                from--;
                to--;
                cost = -cost;

                Edge edge = new Edge();
                edge.from = from;
                edge.to = to;
                edge.cost = cost;
                edges[E++] = edge;
            }

            System.out.println(findNegativeCycle(edges, V) ? "YES" : "NO");
        }
    }

    static final int INF = 1 << 29;
    private static boolean findNegativeCycle(Edge[] edges, int V){
        int[] d = new int[V];
        for (int i = 0; i < V; ++i){
            for (Edge e : edges){
                if(e.cost + d[e.from] < d[e.to]){
                    d[e.to] = e.cost + d[e.from];
                    if (i == V - 1) return true;
                }
            }
        }
        return false;
    }

累,休息。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券