poj 1724 Roads
这题主要是学习如何剪枝，不只是最优性剪枝（当当前的路径长度大于已经求得的最大路径长度就回到上一步），还学习保留中间计算结果剪枝。
minLen [ i ] [ j ] 表示到达城市 i 花费 j 的最小路径长度，并在搜索过程中不断的对该中间结果进行更新。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayList; class Edge { int v; int weight; int money; public Edge(int v, int weight, int money) { this.v = v; this.weight = weight; this.money = money; } } /** * @author wangshaoyu */ public class POJ1724Roads { static int k; static int n; static ArrayList<Edge>[] G; static boolean[] visited; static int ans = Integer.MAX_VALUE; static int[][] minLen; // minLen[i][j] 表示从起点到 i 点，花销为 j 的最短路的长度 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(br); static int nextInt() throws IOException { st.nextToken(); return (int)st.nval; } public static void main(String[] args) throws IOException { k = nextInt(); // k coins n = nextInt(); // n cities int r = nextInt(); // r roads 有向 G = new ArrayList[n]; for (int i = 0; i < n; i++) { G[i] = new ArrayList<Edge>(); } visited = new boolean[n]; minLen = new int[n][k+1]; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { minLen[i][j] = Integer.MAX_VALUE; } } for (int i = 0; i < r; i++) { int s = nextInt() - 1; int d = nextInt() - 1; int l = nextInt(); // 路的长度 int t = nextInt(); // 花的硬币 // 排除自环 if (s != d) { Edge e = new Edge(d, l, t); G[s].add(e); } } visited[0] = true; dfs(0, 0, 0); if (ans == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(ans); } } /** * @param v 到达这个城市 * @param count 到达这个城市的目前花费 * @param length 到达这个城市走了多长的路 */ static void dfs(int v, int count, int length) { // 到达终点 if (v == n - 1) { ans = Math.min(ans, length); return; } // 对当前这个城市 v 的能走到的下一个城市 for (Edge e : G[v]) { if (visited[e.v] == false) { int cost = count + e.money; // 如果花费的钱大于 k if (cost > k) { continue; } // 最优性剪枝 // 保存中间计算结果进行剪枝: 如果到达下一个城市花的钱相同但是走的路径更长 if (length + e.weight >= ans || length + e.weight >= minLen[e.v][cost]) { continue; } minLen[e.v][cost] = length + e.weight; // 更新中间结果 visited[v] = true; dfs(e.v, cost, length + e.weight); visited[v] = false; } } } }