TopCoder SRM 339 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=7423&rd=10663
N個車站，若干輛車，每輛車有始發、終點、開車時間、運行時間和票價5個參數，求從第一站到最后一站在T時間內最便宜的乘車方案。

初看是很簡單的DP，只要用數組從第一行向后逐行計算即可
可是后來看了測試數據發現了逆行車
所以在計算順序上加了隊列 相當于是一個寬搜

解決時候主要的問題出在了DP數組的定義上
一開始的思路是用車站和車去開二維數組
這樣的話每個值又要用時間和價格兩個參數去記錄
計算過程也非常復雜
后來經過提示改成用車站和時間去記錄價格
就方便多了

 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class OnTime
 8{
 9    //the queue has to record two dimensions 
10    public class pair{
11        int n;
12        int t;
13        public pair(int n, int t){
14            this.n = n;
15            this.t = t;
16        }
17    }
18    
19    public int minCost(int N, int T, String[] buses)
20    {
21        int L = buses.length;
22        int[] a = new int[L];
23        int[] b = new int[L];
24        int[] depart = new int[L];
25        int[] time = new int[L];
26        int[] cost = new int[L];
27        
28        //data parse
29        int i;
30        for(i = 0; i < L; ++i){
31            String temps = buses[i];
32            String[] ints = temps.split(" ");
33            a[i] = Integer.parseInt(ints[0]);
34            b[i] = Integer.parseInt(ints[1]);
35            depart[i] = Integer.parseInt(ints[2]);
36            time[i] = Integer.parseInt(ints[3]);
37            cost[i] = Integer.parseInt(ints[4]);
38        }
39        
40        int[][] table = new int[N][T+1];
41        for(int[] ta : table)
42            Arrays.fill(ta, Integer.MAX_VALUE);
43        table[0][0] = 0;
44        
45        //first station is special
46        Queue<pair> q = new LinkedList<pair>();
47        for(i = 0 ; i < L; ++ i){
48            if(a[i] == 0 && depart[i] >= 0 && depart[i]+time[i] <= T){
49                table[b[i]][depart[i]+time[i]] = table[0][0] + cost[i];
50                q.add(new pair(b[i],depart[i]+time[i]));
51            }
52        }
53        
54        //bfs search
55        while(!q.isEmpty()){
56            pair out = q.poll();
57            for(i = 0; i < L; ++ i){
58                if(a[i] == out.n && depart[i] > out.t && depart[i] + time[i] <=T &&
59                        cost[i] + table[out.n][out.t] < table[b[i]][depart[i]+time[i]]){
60                    table[b[i]][depart[i]+time[i]] = table[out.n][out.t] + cost[i];
61                    q.add(new pair(b[i],depart[i]+time[i]));
62                }
63            }
64        }
65        
66        
67        //find min 
68        int min = table[N-1][0];
69        for(i = 1 ; i <= T ; ++ i){
70            if(table[N-1][i] < min)
71                min = table[N-1][i];
72        }
73        
74        
75        return (min==Integer.MAX_VALUE?-1:min);
76    
77    }
78}