DFS练习： POJ1010 POJ1011 POJ1020 POJ1321 POJ1416 POJ1724

POJ1010

package poj1010;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/4 18:11
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 邮票数
     */
    static int m;
    /**
     * 客户数
     */
    static int n;
    /**
     * 邮票面值
     */
    static int[] stamps;
    /**
     * 客户需求
     */
    static int[] needs;

    /**
     * 标记选过的邮票
     */
    static int[] check;
    /**
     * 当前客户的当前组合
     */
    static int[] currCombination;
    /**
     * 当前客户的最佳组合
     */
    static int[] bestCombination;
    /**
     * 当前客户的当前组合的邮票下标
     */
    static int[] cCombIndex;
    /**
     * 当前客户的最佳组合的邮票下标
     */
    static int[] bCombIndex;
    /**
     * 当前累计面值
     */
    static int faceValue;
    /**
     * 当前组合邮票种类数
     */
    static int currTypes;
    /**
     * 最优组合的邮票种类数
     */
    static int maxTypes;
    /**
     * 当前组合的最高面值
     */
    static int currMaxValue;
    /**
     * 最优解中的最高面值
     */
    static int maxValue;
    /**
     * 最优解中的邮票张数
     */
    static int minStaNum;

    /**
     * 是否持平
     */
    static int tie;

    static int len;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            len = str.length();
            m = 0;
            stamps = new int[len/2 + 5];
            int num = 0;
            for (int i = 0; i < len; i++) {
                char a  = str.charAt(i);
                if (a==' '){
                    m++;
                    num = 0;
                    continue;
                }
                if (!(num==0&&a-'0'==0)){
                    if (num==0){
                        num = a-'0';
                    }else {
                        num = num*10+(a-'0');
                    }
                    stamps[m] = num;
                }
            }
            str = sc.nextLine();
            len = str.length();
            n = 0;
            num = 0;
            needs = new int[len/2  + 5];
            for (int i = 0; i < len; i++) {
                char a  = str.charAt(i);
                if (a==' '){
                    n++;
                    num = 0;
                    continue;
                }
                if (!(num==0&&a-'0'==0)){
                    if (num==0){
                        num = a-'0';
                    }else {
                        num = num*10+(a-'0');
                    }
                    needs[n] = num;
                }
            }
//            System.out.println("m="+m+"  n="+n);
            bubbleSort(stamps, m);

//            System.out.println(Arrays.toString(stamps));
//            System.out.println(Arrays.toString(needs));
            for (int i = 0; i < n; i++) {
                initData();
                dfs(0, i);
                printAns(i);
            }

        }
    }

    private static void initData() {
        check = new int[m + 5];
        currCombination = new int[4];
        bestCombination = new int[4];
        cCombIndex = new int[4];
        bCombIndex = new int[4];
        faceValue = 0;
        currTypes = 0;
        maxTypes = 0;
        currMaxValue = 0;
        maxValue = 0;
        minStaNum = 0;
        tie = 0;
    }

    private static void printAns(int cusIndex) {
        if (maxTypes == 0) {
            System.out.println(needs[cusIndex] + " ---- none");
        } else {
            System.out.print(needs[cusIndex] + " (" + maxTypes + "): ");
            if (tie == 1){
                System.out.println("tie");
            }else {
                for (int i = 0; i < minStaNum; i++) {
                    if (i == minStaNum - 1) {
                        System.out.println(bestCombination[i]);
                    } else {
                        System.out.print(bestCombination[i] + " ");
                    }
                }
            }
        }

    }

    /**
     * @param staNum   当前组合选定的邮票数
     * @param cusIndex 客户下标
     */
    private static void dfs(int staNum, int cusIndex) {

        if (staNum == 4) {
            return;
        }
        /*遍历所有邮票*/
        for (int i = 0; i < m; i++) {
            /*如果当前邮票加入不超额*/
            if (faceValue + stamps[i] <= needs[cusIndex]) {
                /*当前邮票放入临时组合*/
                currCombination[staNum] = stamps[i];
                /*记录当前邮票下标,为了和初始的0区分+1*/
                cCombIndex[staNum] = i + 1;

                /*累计面值*/
                faceValue += stamps[i];
    /*            if (currCombination[1]==1&&currCombination[3]==3){
                    System.out.println(Arrays.toString(currCombination)+"faceV="+faceValue);
                }*/
                /*回溯工具变量*/
                int a = 0;
                int b = 0;
                /*记录单张邮票的最大面值*/
                if (stamps[i] > currMaxValue) {
                    a = currMaxValue;
                    currMaxValue = stamps[i];
                }
                /*如果当前邮票没选过，种类+1*/
                if (check[i] == 0) {
                    check[i] = 1;
                    currTypes++;
                    b = 1;
                }
                /*当前选中邮票数*/
                int currStaNum = staNum + 1;

                /*当前累计面值=客户需求面值，根据条件更新当前最优解*/
                if (faceValue == needs[cusIndex]) {
                   /* System.out.println(Arrays.toString(currCombination));
                    System.out.println("currTypes="+currTypes+"  currStaNum="+currStaNum+"  currMaxValue"+currMaxValue);*/
                     /*最佳组合定义为不同邮票类型的最大数量。如果是平局，
                     那么总邮票数最少的组合是最好的。如果仍然相同，则具有
                     最高面值邮票的组合为最佳。如果还是平局，请打印 “tie”。*/
                    /*还未找到一个最优解*/
                    boolean bl1 = maxTypes == 0;
                    /*当前解的邮票种类更多*/
                    boolean bl2 = currTypes > maxTypes;
                    /*当前解和最优解的邮票种类一样多*/
                    boolean bl3 = currTypes == maxTypes;
                    boolean bl4 = currStaNum < minStaNum;
                    /*当前解和最优解的邮票数量一样多*/
                    boolean bl5 = currStaNum == minStaNum;
                    boolean bl6 = currMaxValue > maxValue;
                    /*当前解和最优解的最高单张邮票面值一样大*/
                    boolean bl7 = currMaxValue == maxValue;
                    if (bl1||bl2) {
                        recordStamps(currStaNum);

                    } else if (bl3 && bl4) {
                        recordStamps(currStaNum);
                    } else if (bl3 && bl5 && bl6) {
                        recordStamps(currStaNum);
                    } else if (bl3 && bl5 && bl7&&notRepeat()) {
                      tie = 1;
                    }
                } else {
                    /*4层深度不用剪枝，如果要剪枝，可以把邮票按面值从大到小排序，
                    然后 “当前邮票面值”ד剩余邮票数”<"剩余需求面值" 就可以剪枝*/
                    dfs(currStaNum, cusIndex);
                }
                /*回溯*/
                currCombination[staNum] = 0;
                cCombIndex[staNum] = 0;
                faceValue -= stamps[i];
                currMaxValue = a;
                if (b == 1) {
                    check[i] = 0;
                    currTypes--;
                }
            }
        }
    }

    /**
     * @return 判断两个组合是否重复
     */
    private static boolean notRepeat() {
        int repeat = 0;
        int[] temp = new int[4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (cCombIndex[i] == bCombIndex[j]&&temp[j]==0) {
                    temp[j]=1;
                    repeat++;
                    break;
                }
            }
        }
        return repeat != 4;
    }

    /**
     * 记录邮票组合
     * @param currStaNum
     */
    private static void recordStamps(int currStaNum) {
        bestCombination = new int[4];
        bCombIndex = new int[4];
        for (int i = 0; i < currStaNum; i++) {
            bestCombination[i] = currCombination[i];
            bCombIndex[i] = cCombIndex[i];
        }
        maxTypes = currTypes;
        minStaNum = currStaNum;
        maxValue = currMaxValue;
        tie = 0;
    }


    private static void bubbleSort(int[] arr, int len) {

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
/*
1 2 3 0
7 4 0
1 1 0
6 2 3 0


7 (3): 1 1 2 3
4 (2): 1 3
6 ---- none
2 (2): 1 1
3 (2): tie

解题要点 1: 确定核心算法.
本题最优解的判定过程相当复杂, 无法得出局部最优解, 因此不能采用 DP. 而由于本题的解具有相当有限的深度 (至多为 4), 因此可考虑采用 DFS.

解题要点 2: 剪枝.
当已经分配了 4 张邮票时, 可以剪枝.
进一步地, 若事先已对邮票库存进行了依面值从大到小的排序, 则以下剪枝规则成立:
设已递归至某种面值 value 的邮票, 之前已选取的邮票的总面值为 tmp, 已选取的邮票的张数为 dealt, 用户需求的总面值为 req, 则当下式为 true 时, 可以剪枝:
value×(4−dealt)<req−tmp
*/

POJ1011

package poj1011;

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/5 20:17
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 记录当前case的棒数
     */
    static int n;
    /**
     * 每根棒长度
     */
    static int[] sticks;

    /**
     * 被选中的短棍
     */
    static boolean[] check;

    /**
     * 当前限制的组合棒长度
     */
    static int stickLen;

    /**
     * 当前长度限制下组合棍数量
     */
    static int stickNum;

    /**
     * 最短组合棍长度
     */
    static int shortestLen;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            n = sc.nextInt();
            if (n == 0) {
                break;
            }
            sticks = new int[n + 5];
            /*统计所有短棍总长度*/
            int perimeter = 0;
            for (int i = 0; i < n; i++) {
                sticks[i] = sc.nextInt();
                perimeter += sticks[i];
            }
            bubbleSort();
            /*合成棍最短是最长的那根短棍，最长是len/2，否则不用算*/
            for (int i = sticks[0]; i <= perimeter / 2; i++) {
                /*如果当前长度能被len整除就是有可能的*/
                if (perimeter % i == 0) {
                    /*初始化标记数组*/
                    check = new boolean[n + 5];
                    shortestLen = 0;
                    stickLen = i;
                    /*组合棍数*/
                    stickNum = perimeter / i;
                    dfs(0, 0, 0);
                    if (shortestLen > 0) {
                        break;
                    }
                }
            }
            if (shortestLen == 0) {
                shortestLen = 1;
            }
            System.out.println(shortestLen);
        }
    }

    /**
     * @param index     每次从前一根棒的下标i+1开始搜索
     * @param currLen   当前棒已完成长度
     * @param finishNum 当前完成组合棒的数量
     */
    private static void dfs(int index, int currLen, int finishNum) {
        if (shortestLen == 0) {
            if (currLen == 0) {
                int a = 0;
                while (check[a]) {
                    a++;
                }
                check[a] = true;
                dfs(a + 1, sticks[a], finishNum);
            }
            /*记录匹配不成功的小棒长度*/
            int same = 0;
            for (int i = index; i < n; i++) {
                /*如果某根长度的小棒不选，跳过所有等长的小棒*/
                if (!check[i] && same != sticks[i]) {
                    if (currLen + sticks[i] <= stickLen) {
                        check[i] = true;
                        currLen += sticks[i];
                        if (currLen == stickLen) {
                            finishNum++;
                            if (finishNum == stickNum - 1) {
                                shortestLen = stickLen;
                                return;
                            }
                            dfs(0, 0, finishNum);
                            finishNum--;
                        }
                        dfs(i + 1, currLen, finishNum);
                        check[i] = false;
                        currLen -= sticks[i];


                    }
                    /*剪枝点，如果第一根没选上，说明当前组合长度不会成功*/
                    if (currLen == 0) {
                        return;
                    }
                    /*剪枝点，如果已经拼成了一个组合棒，应该进入递归变成0的，
                    但是下一个递归却失败了，说明当前棒能成，下一根不行*/
                    if (currLen + sticks[i] == stickLen) {
                        return;
                    }
                    /*记录匹配不成功的小棒长度*/
                    same = sticks[i];
                    /* 如果剩下的和比我需要的棒子还小的话，就不用凑了*/
                    int remain = 0;
                    int ind = i;
                    while (ind < n) {
                        if (!check[ind]) {
                            remain += sticks[ind];
                        }
                        ind++;
                    }
                    if (remain < stickLen - currLen) {
                        return;
                    }
                }
            }
        }
    }

    public static void bubbleSort() {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                if (sticks[j] < sticks[j + 1]) {
                    int temp = sticks[j];
                    sticks[j] = sticks[j + 1];
                    sticks[j + 1] = temp;
                }
            }
        }
    }
}
/*
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

9
5 2 1 5 2 1 5 2 1
0

*/

POJ1020

package poj1020;

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/11 20:21
 * @Description
 * @Since version-1.0
 */
public class Main {

    /**
     * 大蛋糕的边 [1,40]
     */
    static int lCakeSide;
    /**
     * 大蛋糕的列，用列的高度来记录分配小蛋糕的情况
     */
    static int[] lCakeColumn;
    /**
     * 小蛋糕数量  [1,16]
     */
    static int sCakeNum;
    /**
     * 各种尺寸的蛋糕数量
     * 小蛋糕的边 [1,10]
     */
    static int[] sCakeSide;

    /**
     *
     */
    static boolean succeed;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            lCakeSide = sc.nextInt();
            sCakeNum = sc.nextInt();
            lCakeColumn = new int[lCakeSide+5];
            sCakeSide = new int[sCakeNum+5];
            for (int j = 0; j < sCakeNum; j++) {
                int ind = sc.nextInt();
                sCakeSide[ind]++;
            }
            succeed = false;
            dfs(0);
            if (succeed){
                System.out.println("KHOOOOB!");
            }else {
                System.out.println("HUTUTU!");
            }
        }
    }

    /**
     * @param layer 递归的层，放入小蛋糕的数量
     */
    private static void dfs(int layer) {
        if (layer==sCakeNum){
            succeed = true;
            return;
        }
        /*找出最小的列*/
        int min = 50;
        int colIndex = 0;
        for (int i = 0; i < lCakeSide; i++) {
            if (lCakeColumn[i]<min){
                min = lCakeColumn[i];
                colIndex = i;
            }
        }
        /*枚举各种尺寸的蛋糕自下而上地放入盒子*/
        for (int size = 10; size >=1 ; size--) {
            if (sCakeSide[size]<=0){
                continue;
            }
            /*检查尺寸为size的蛋糕放入盒子时在纵向和横向是否越界*/
            if (lCakeSide-lCakeColumn[colIndex]>=size&&lCakeSide-colIndex>=size){

                int wide = 0;
                int rigIndex = colIndex+size;
                /*判断有没有足够多的列，一开始是打算用bool，后来发现有漏洞*/
                for (int r = colIndex; r < rigIndex; r++) {
                   if (lCakeColumn[r] <= lCakeColumn[colIndex]){
                       wide++;
                   }
                }
                if (wide==size){
                    /*放入该尺寸的蛋糕*/
                    sCakeSide[size]--;
                    for (int r = colIndex; r < rigIndex; r++) {
                        lCakeColumn[r]+=size;
                    }
                    dfs(layer+1);
                    /*如果成功就剪枝*/
                    if (succeed) {
                        return;
                    }
                    System.out.println();
                    sCakeSide[size]++;
                    for (int r = colIndex; r < rigIndex; r++) {
                        lCakeColumn[r]-=size;
                    }
                }
            }
        }
    }
}
/*
2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1
用数组存储各种尺寸的小蛋糕的数量，比直接存储尺寸方便很多，少了排序，标记等步骤。
*/

POJ1321

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/4 14:13
 * @Description
 * @Since version-1.0
 */
public class Main {
    static int n;
    static int k;
    /**
     * 棋盘
     */
    static char[][] board;
    /**
     * 标记被用过的列
     */
    static int[] check;
    static long schemes;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            n = sc.nextInt();
            k = sc.nextInt();
            if (n == -1 && k == -1) {
                break;
            }
            board = new char[n + 5][n + 5];
            check = new int[n + 5];
            for (int i = 0; i < n; i++) {
                String str = sc.next();
                for (int j = 0; j < n; j++) {
                    board[j][i] = str.charAt(j);
                }
            }
            schemes = 0;

            dfs(0, 0);
            System.out.println(schemes);


        }
    }

    /**
     * @param c  从第几列开始
     * @param ck 当前已放置棋子数
     */
    private static void dfs(int c, int ck) {
        if (ck == k) {
            schemes++;
            return;
        }
        if (c == n) {
            /*出界*/
            return;
        }
        for (int i = 0; i < n; i++) {
            if (board[c][i] == '#' && check[i] == 0) {
                check[i] = 1;
                dfs(c + 1, ck + 1);
                check[i] = 0;
            }
        }
        dfs(c + 1, ck);
    }
}

POJ1416

package poj1416;

import java.util.Scanner;
import java.util.Stack;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/6 11:08
 * @Description
 * 这题没剪枝就过了，但是被1011题训练出来的直觉还是让我找到一些剪枝点，
 * 过了再剪枝和超时再剪枝的心态完全不一样，下次超时不要急，慢慢剪总会AC的
 * @Since version-1.0
 */
public class Main {
    static int target;
    static String num;
    static int len;
    static int sum;
    /**
     * 当前最小和
     */
    static int currMinSum;
    static boolean error;
    static boolean rejected;
    static Stack<Integer> cuttingResults;
    static Stack<Integer> currCuttingR;


    /**
     * @param layer     当前层数（第几刀）
     * @param remainNum 剩余的数字
     */
    private static void dfs(int layer, String remainNum) {

        if (layer == 0) {
            /*如果当前数字=目标数，就不用切。（字符串转整数要自己写个方法）*/
            if (Integer.parseInt(remainNum) == target) {
                cuttingResults.push(target);
                sum = target;
                return;
            }
            /*计算最小分割的和*/
            for (int i = 0; i < len; i++) {
                sum += remainNum.charAt(i) - '0';
            }
            /*如果大于目标数，输出error*/
            if (sum > target) {
                error = true;
                return;
            }
            sum = 0;
        }

        boolean off = false;
        int cLen = remainNum.length();
        for (int i = 1; i <= cLen && !off; i++) {
            int cutNum = 0;
            String cutStr = "";
            /*全切给数字*/
            if (i == cLen) {
                cutNum = Integer.parseInt(remainNum);
            } else {
                /*分割数字和字符串*/
                for (int j = 0; j < cLen; j++) {
                    char cj = remainNum.charAt(j);
                    if (j < i) {
                        if (cutNum == 0) {
                            cutNum += cj - '0';
                        } else {
                            cutNum = cutNum * 10 + cj - '0';
                        }
                    } else {
                        cutStr += cj;
                    }
                }
            }

            /*记录当前数字和*/
            currMinSum += cutNum;
            currCuttingR.push(cutNum);
            /*如果字符串剩1位*/
            if (cutStr.length() == 1) {
                int lastNum = cutStr.charAt(0) - '0';
                currMinSum += lastNum;
                currCuttingR.push(lastNum);
            }

            /*如果分割完并且当前数字和大于最优数字和*/
            if ((cutStr.length() == 1 || cutStr.length() == 0) && (sum == 0 || currMinSum >= sum) && currMinSum <= target) {
                if (currMinSum == sum) {
                    rejected = true;
                } else {
                    rejected = false;
                    sum = currMinSum;
                    cuttingResults = (Stack<Integer>) currCuttingR.clone();
                }
            }
            if (cutStr.length() > 1 && currMinSum < target) {
                dfs(layer+1, cutStr);
            }
            /*剪枝，下一循环只会让currMinSum更大*/
            if (currMinSum > target) {
                off=true;
            }
            /*回溯*/
            currMinSum -= cutNum;
            currCuttingR.pop();
            if (cutStr.length() == 1) {
                currMinSum -= cutStr.charAt(0) - '0';
                currCuttingR.pop();
            }

        }
    }

    private static void initData() {

        currMinSum = 0;
        sum = 0;
        error = false;
        rejected = false;
        cuttingResults = new Stack<Integer>();
        currCuttingR = new Stack<Integer>();

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            target = sc.nextInt();
            int a = sc.nextInt();
            if (target == 0 && a == 0) {
                break;
            }
            num = a + "";
            len = num.length();
            initData();
            dfs(0, num);
            if (error) {
                System.out.println("error");
            } else if (rejected) {
                System.out.println("rejected");
            } else {
                System.out.print(sum + " ");
                int size = cuttingResults.size();
                for (int i = 0; i < size; i++) {
                    if (i == size - 1) {
                        System.out.println(cuttingResults.get(i));
                    } else {
                        System.out.print(cuttingResults.get(i) + " ");
                    }
                }

            }
        }
    }
}
/*
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
*/

POJ1724

package poj1724;

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/18 23:40
 * @Description
 * @Since version-1.0
 */
public class Main2 {
    /**
     * 钱数
     */
    static int k;
    /**
     * 城市数
     */
    static int n;
    /**
     * 道路数
     */
    static int r;
    /**
     * 道路邻接矩阵
     */
    static int[][][] roads;
    /**
     * 最短路径
     */
    static int shortestLen = -1;

    /**
     * 访问过的点
     */
    static boolean[] visit;
    /**
     * 存储i点在花费k元时的路程
     */
    static int[][] save;

    private static void dfs(int city, int spend, int length) {

        if (city == n) {
            if (shortestLen == -1 || shortestLen > length) {
                shortestLen = length;
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visit[i] && roads[city][i][0] != 0) {
                /*重复边中最短的*/
                int t1 = spend + roads[city][i][2];
                if (t1 <= k) {
                    int l1 = length + roads[city][i][1];
                    /*如果当前l1大于最短路径剪枝*/
                    if (l1 < shortestLen || shortestLen == -1) {
                        /*如果之前记录的i点在t1元时的路程比现在的l1小就剪枝*/
                        if (save[i][t1] == 0 || save[i][t1] > l1) {
                            save[i][t1] = l1;
                            visit[i] = true;
                            dfs(i, t1, l1);
                            visit[i] = false;
                        }
                    }

                }
                /*重复边中最便宜的*/
                int t2 = spend + roads[city][i][4];
                /*如果不重复，t2<t1一定成立*/
                if (t2 < t1 && t2 <= k) {
                    int l2 = length + roads[city][i][3];
                    /*如果当前l2大于最短路径剪枝*/
                    if (l2 < shortestLen || shortestLen == -1) {

                        /*如果之前记录的i点在t2元时的路程比现在的l2小就剪枝*/
                        if (save[i][t2] == 0 || save[i][t2] > l2) {
                            save[i][t2] = l2;
                            visit[i] = true;
                            dfs(i, t2, l2);
                            visit[i] = false;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        k = sc.nextInt();
        n = sc.nextInt();
        r = sc.nextInt();
        roads = new int[n + 5][n + 5][5];
        visit = new boolean[n + 5];
        save = new int[n + 5][k + 5];
        for (int i = 0; i < r; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int l = sc.nextInt();
            int t = sc.nextInt();
            if (roads[s][e][0] == 1) {

                /*筛选重负边中最短的*/
                if (l == roads[s][e][1]) {
                    if (t < roads[s][e][2]) {
                        roads[s][e][1] = l;
                        roads[s][e][2] = t;
                    }
                } else if (l < roads[s][e][1]) {
                    roads[s][e][1] = l;
                    roads[s][e][2] = t;
                }


                /*筛选重负边中最便宜的*/
                if (t == roads[s][e][4]) {
                    if (l < roads[s][e][3]) {
                        roads[s][e][3] = l;
                        roads[s][e][4] = t;
                    }
                } else if (t < roads[s][e][4]) {
                    roads[s][e][3] = l;
                    roads[s][e][4] = t;
                }

            } else {
                roads[s][e][1] = l;
                roads[s][e][2] = t;
                roads[s][e][3] = l;
                roads[s][e][4] = t;
                /*标记边存在*/
                roads[s][e][0] = 1;
            }

        }
        dfs(1, 0, 0);
        System.out.println(shortestLen);
    }
}
/*
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

11

19
6
7
1 2 2 2
1 3 2 2
1 4 2 2
2 5 5 10
4 5 7 7
3 5 10 5
5 6 5 10

14

15
12
16
1 8 20 0
1 2 10 0
2 8 5 0
1 7 100 0
2 3 5 1
3 4 5 1
4 5 5 1
5 6 5 1
6 12 5 1
8 12 10 20
8 9 1 1
9 10 1 1
10 11 1 1
11 7 2 10
7 12 10 1
11 4 1 0

30
*/

原文地址：http://www.cnblogs.com/jinjun99/p/16807571.html