PAT 甲級(jí)考試【1003 Emergency】

這篇具有很好參考價(jià)值的文章主要介紹了PAT 甲級(jí)考試【1003 Emergency】。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

題目：

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers:?

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between?

Sample Input:

Sample Output:

2 4

Dijkstra 算法

Dijkstra（/?dikstrɑ/或/?d?ikstrɑ/）算法由荷蘭計(jì)算機(jī)科學(xué)家 E. W. Dijkstra 于 1956 年發(fā)現(xiàn)，1959 年公開發(fā)表。是一種求解?非負(fù)權(quán)圖?上單源最短路徑的算法。

過(guò)程

將結(jié)點(diǎn)分成兩個(gè)集合：已確定最短路長(zhǎng)度的點(diǎn)集（記為? PAT 甲級(jí)考試【1003 Emergency】 ?集合）的和未確定最短路長(zhǎng)度的點(diǎn)集（記為??集合）。一開始所有的點(diǎn)都屬于??集合。

初始化? PAT 甲級(jí)考試【1003 Emergency】，其他點(diǎn)的??均為?。

然后重復(fù)這些操作：

從??集合中，選取一個(gè)最短路長(zhǎng)度最小的結(jié)點(diǎn)，移到??集合中。
對(duì)那些剛剛被加入??集合的結(jié)點(diǎn)的所有出邊執(zhí)行松弛操作。

直到? PAT 甲級(jí)考試【1003 Emergency】 ?集合為空，算法結(jié)束。

時(shí)間復(fù)雜度

有多種方法來(lái)維護(hù) 1 操作中最短路長(zhǎng)度最小的結(jié)點(diǎn)，不同的實(shí)現(xiàn)導(dǎo)致了 Dijkstra 算法時(shí)間復(fù)雜度上的差異。

暴力：不使用任何數(shù)據(jù)結(jié)構(gòu)進(jìn)行維護(hù)，每次 2 操作執(zhí)行完畢后，直接在??集合中暴力尋找最短路長(zhǎng)度最小的結(jié)點(diǎn)。2 操作總時(shí)間復(fù)雜度為?，1 操作總時(shí)間復(fù)雜度為?，全過(guò)程的時(shí)間復(fù)雜度為?。
二叉堆：每成功松弛一條邊?，就將??插入二叉堆中（如果??已經(jīng)在二叉堆中，直接修改相應(yīng)元素的權(quán)值即可），1 操作直接取堆頂結(jié)點(diǎn)即可。共計(jì)??次二叉堆上的插入（修改）操作，?次刪除堆頂操作，而插入（修改）和刪除的時(shí)間復(fù)雜度均為?，時(shí)間復(fù)雜度為?。
優(yōu)先隊(duì)列：和二叉堆類似，但使用優(yōu)先隊(duì)列時(shí)，如果同一個(gè)點(diǎn)的最短路被更新多次，因?yàn)橄惹案聲r(shí)插入的元素不能被刪除，也不能被修改，只能留在優(yōu)先隊(duì)列中，故優(yōu)先隊(duì)列內(nèi)的元素個(gè)數(shù)是??的，時(shí)間復(fù)雜度為?。
Fibonacci 堆：和前面二者類似，但 Fibonacci 堆插入的時(shí)間復(fù)雜度為?，故時(shí)間復(fù)雜度為?，時(shí)間復(fù)雜度最優(yōu)。但因?yàn)?Fibonacci 堆較二叉堆不易實(shí)現(xiàn)，效率優(yōu)勢(shì)也不夠大¹，算法競(jìng)賽中較少使用。
線段樹：和二叉堆原理類似，不過(guò)將每次成功松弛后插入二叉堆的操作改為在線段樹上執(zhí)行單點(diǎn)修改，而 1 操作則是線段樹上的全局查詢最小值。時(shí)間復(fù)雜度為?。

在稀疏圖中， PAT 甲級(jí)考試【1003 Emergency】，使用二叉堆實(shí)現(xiàn)的 Dijkstra 算法較 Bellman–Ford 算法具有較大的效率優(yōu)勢(shì)；而在稠密圖中，，這時(shí)候使用暴力做法較二叉堆實(shí)現(xiàn)更優(yōu)。

正確性證明

下面用數(shù)學(xué)歸納法證明，在?所有邊權(quán)值非負(fù)?的前提下，Dijkstra 算法的正確性²。

簡(jiǎn)單來(lái)說(shuō)，我們要證明的，就是在執(zhí)行 1 操作時(shí)，取出的結(jié)點(diǎn)? PAT 甲級(jí)考試【1003 Emergency】 ?最短路均已經(jīng)被確定，即滿足?。

初始時(shí)? PAT 甲級(jí)考試【1003 Emergency】，假設(shè)成立。

接下來(lái)用反證法。

設(shè)? PAT 甲級(jí)考試【1003 Emergency】 ?點(diǎn)為算法中第一個(gè)在加入??集合時(shí)不滿足??的點(diǎn)。因?yàn)??點(diǎn)一定滿足?，且它一定是第一個(gè)加入??集合的點(diǎn)，因此將??加入??集合前，，如果不存在??到??的路徑，則? PAT 甲級(jí)考試【1003 Emergency】，與假設(shè)矛盾。

于是一定存在路徑? PAT 甲級(jí)考試【1003 Emergency】，其中??為??路徑上第一個(gè)屬于??集合的點(diǎn)，而??為??的前驅(qū)結(jié)點(diǎn)（顯然?）。需要注意的是，可能存在??或??的情況，即??或??可能是空路徑。

因?yàn)樵? PAT 甲級(jí)考試【1003 Emergency】 ?結(jié)點(diǎn)之前加入的結(jié)點(diǎn)都滿足?，所以在??點(diǎn)加入到??集合時(shí)，有?，此時(shí)邊??會(huì)被松弛，從而可以證明，將??加入到??時(shí)，一定有?。

下面證明? PAT 甲級(jí)考試【1003 Emergency】 ?成立。在路徑??中，因?yàn)閳D上所有邊邊權(quán)非負(fù)，因此?。從而?。但是因?yàn)??結(jié)點(diǎn)在 1 過(guò)程中被取出??集合時(shí)，?結(jié)點(diǎn)還沒有被取出??集合，因此此時(shí)有? PAT 甲級(jí)考試【1003 Emergency】，從而得到?，這與??的假設(shè)矛盾，故假設(shè)不成立。

因此我們證明了，1 操作每次取出的點(diǎn)，其最短路均已經(jīng)被確定。命題得證。

注意到證明過(guò)程中的關(guān)鍵不等式? PAT 甲級(jí)考試【1003 Emergency】 ?是在圖上所有邊邊權(quán)非負(fù)的情況下得出的。當(dāng)圖上存在負(fù)權(quán)邊時(shí)，這一不等式不再成立，Dijkstra 算法的正確性將無(wú)法得到保證，算法可能會(huì)給出錯(cuò)誤的結(jié)果。

實(shí)現(xiàn)

這里同時(shí)給出? PAT 甲級(jí)考試【1003 Emergency】 ?的暴力做法實(shí)現(xiàn)和??的優(yōu)先隊(duì)列做法實(shí)現(xiàn)

PAT 甲級(jí)考試：

-----dfs+dijkstra算法。

先求出最短路徑
再計(jì)算出最短路徑數(shù)目并計(jì)算出路徑上點(diǎn)權(quán)值的最大team和

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m;
    static int source, target;

    static int[] number;
    static int[][] matrix = new int[500][500];

    static int[] distance;

    static int shorts;

    static int maxpeople = 0;

    static boolean[] traved;

    static List<Integer>[] adj;

    static int ways = 0;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] words = br.readLine().split("\\s+");
        n = Integer.valueOf(words[0]);
        m = Integer.valueOf(words[1]);
        source = Integer.valueOf(words[2]);
        target = Integer.valueOf(words[3]);

        number = new int[n];
        words = br.readLine().split("\\s+");
        for (int i = 0; i < n; i++) {
            number[i] = Integer.valueOf(words[i]);
        }
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int c1, c2, l;
            words = br.readLine().split("\\s+");
            c1 = Integer.valueOf(words[0]);
            c2 = Integer.valueOf(words[1]);
            l = Integer.valueOf(words[2]);

            matrix[c1][c2] = l;
            matrix[c2][c1] = l;

            adj[c1].add(c2);
            adj[c2].add(c1);
        }
        //bfs;


        distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE / 2);
        distance[source] = 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return distance[o1] - distance[o2];
            }
        });

        queue.add(source);
        boolean[] visited = new boolean[n];

        while (!queue.isEmpty()) {
            int city = queue.poll();

            if( visited[city]) continue;

            if (distance[city] >= Integer.MAX_VALUE / 2) {
                break;
            }

            visited[city] = true;

            for (int adjcity : adj[city]) {
                if (distance[adjcity] > distance[city] + matrix[city][adjcity]) {
                    distance[adjcity] = distance[city] + matrix[city][adjcity];
                    queue.add(adjcity);
                }
            }
        }

        shorts = distance[target];
        //深度搜索
        traved = new boolean[n];
        traved[source] = true;
        travel(source, 0, number[source], 0);
        System.out.println(allpath.size() + " " + maxpeople);
    }

    static Set<List<Integer>> allpath = new HashSet<>();
    static List<Integer> path = new ArrayList<>();

    static public void travel(int city, int d, int people, int depth) {
        if (city == target && d == shorts) {
            List<Integer> sortedpath = new ArrayList<>();
            for (int x : path) {
                sortedpath.add(x);
            }
            Collections.sort(sortedpath);
            if (!allpath.contains(sortedpath)) {
                ways++;
                allpath.add(sortedpath);
            }

            if (people > maxpeople) {
                maxpeople = people;
            }
            return;
        }

        if (d > shorts) {
            return;
        }

        for (int u : adj[city]) {
            if (!traved[u]) {
                traved[u] = true;
                path.add(u);
                travel(u, d + matrix[city][u], people + number[u], depth + 1);
                traved[u] = false;
                int x = path.remove(depth);
            }
        }

    }
}