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}