Solve

图上的动态规划

题目描述

陶陶假期的时候独自去天津玩，出发前他想制定一个旅行计划。假设天津有N个景点，陶陶给每个景点定义了一个开心值Si，也就是说当他游玩这个景点后他的总开心值会加Si，同时，游玩第i个景点会花费Ci的时间。由于没有基友陪，所以他想在限定的时间T内，从起始点S，有选择的游览一些景点，最后到达终点E。当然他想让这次旅行所得的开心值最大。

注意，陶陶可以为了走近路而只是路过一些景点，不去游玩（包括S和E）。而且他有一个怪癖就是要去玩的下一个景点的开心值一定要大于之前玩的景点（例如他游玩景点i获得的开心值为10，那么他游玩的下一个景点的开心值必须大于10）。此外，景点间的路是双向的，路上也要耗费时间，而且各个点之间可能不止一条路，陶陶当然会走最短了啦。

输入
每组测试数据格式如下：
第一行包括5个整数：N M T S E。N代表景点的数量1<N<100，M代表道路的数量0<M<1000，T代表时间限制0<T<=300，S代表起点，E代表终点，0<=S,E<N。
第二行包括N个整数Ci（0<=Ci<=T）,表示游玩景点i所要花费的时间。
第三行包括N个整数Si（0<=Si<100）,表示游玩景点i可以得到的开心值。
接下来M行，每行包括3个整数u,v,w,表示在u和v间有一条双向路，在路上要耗费w的时间(0<=u,v<N,0<=w<=T)。
输出
输出一个整数，表示这次旅行可以获得的最大开心值。当然，如果不能再T时间内到达E，只需要输出”0”（没有引号）。

样例

输入样例 1 
4 4 22 0 3
1 1 1 1
5 7 9 12
0 1 10
1 3 10
0 2 10
2 3 10
输出样例 1
21

题目解答

状态转移方程f[i][j]表示当在第i号景点happy并且还剩j个时间的最大幸福度。
因为可以从任何可达的景点走过来，所以在处理状态的时候非常容易brainfuck。
本题的实现思想就是状态转移，但是形式上采用队列。每当访问到景点e的时候就更新结果，可以不在终点happy。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <queue>

#define MIN(a,b) (a < b ? a : b)
#define MAX(a,b) (a > b ? a : b)

int map[105][105], cost[105], value[105], ans;

struct Node {
    int pos, time, lastValue, value;
};

int main(){
  int n, m, t, s, e;
  cin >> n >> m >> t >> s >> e;
  for (int i = 0; i < n; i++) cin >> cost[i];
  for (int i = 0; i < n; i++) cin >> value[i];

  for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++)
          if (i != j) map[i][j] = t + 1;

  for (int i = 0; i < m; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      map[a][b] = MIN(map[a][b], c);
      map[b][a] = map[a][b];
  }

  // floyd
  for (int k = 0; k < n; k++) {
      for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
              if (map[i][j] > map[i][k] + map[k][j])
                  map[i][j] = map[i][k] + map[k][j];
          }
      }
  }

  if (map[s][e] > t) {
      cout << 0 << endl;
  } else {
      queue<Node> q;
      Node temp;
      temp.pos = s, temp.time = t, temp.lastValue = -1, temp.value = 0;
      q.push(temp);

      while(q.size()) {
          Node head = q.front();
          q.pop();
          int pos = head.pos;
          for(int i = 0; i < n; i++) {
              if(i == e && (head.time - map[pos][i] >= 0)) ans = MAX(ans, head.value);
              if (value[i] > head.lastValue) {
                  Node temp;
                  int time = head.time - map[pos][i] - cost[i];
                  if (time >= 0) {
                      temp.pos = i;
                      temp.lastValue = value[i];
                      temp.value = head.value + value[i];
                      temp.time = time;
                      q.push(temp);
                  }
              }
          }
      }
      cout << ans << endl;
  }

  return 0;
}