Codeforces Round #374 (Div. 2) C. Journey —

Codeforces Round #374 (Div. 2) C. Journey —— DP

题目链接：http://codeforces.com/contest/721/problem/C

Recently Irina arrived to one of the most famous cities of Berland — the Berlatov city. There are n showplaces in the city, numbered from 1 to n, and some of them are connected by one-directional roads. The roads in Berlatov are designed in a way such that there are no cyclic routes between showplaces.

Initially Irina stands at the showplace 1, and the endpoint of her journey is the showplace n. Naturally, Irina wants to visit as much showplaces as she can during her journey. However, Irina's stay in Berlatov is limited and she can't be there for more than T time units.

Help Irina determine how many showplaces she may visit during her journey from showplace 1 to showplace n within a time not exceeding T. It is guaranteed that there is at least one route from showplace 1 to showplace n such that Irina will spend no more than Ttime units passing it.

Input

The first line of the input contains three integers n, m and T (2 ≤ n ≤ 5000, 1 ≤ m ≤ 5000, 1 ≤ T ≤ 109) — the number of showplaces, the number of roads between them and the time of Irina's stay in Berlatov respectively.

The next m lines describes roads in Berlatov. i-th of them contains 3 integers ui, vi, ti (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ ti ≤ 109), meaning that there is a road starting from showplace ui and leading to showplace vi, and Irina spends ti time units to pass it. It is guaranteed that the roads do not form cyclic routes.

It is guaranteed, that there is at most one road between each pair of showplaces.

Output

Print the single integer k (2 ≤ k ≤ n) — the maximum number of showplaces that Irina can visit during her journey from showplace 1 to showplace n within time not exceeding T, in the first line.

Print k distinct integers in the second line — indices of showplaces that Irina will visit on her route, in the order of encountering them.

If there are multiple answers, print any of them.

Examples
input
4 3 13
1 2 5
2 3 7
2 4 8
output
3
1 2 4 
input
6 6 7
1 2 2
1 3 3
3 6 3
2 4 2
4 6 2
6 5 1
output
4
1 2 4 6 
input
5 5 6
1 3 3
3 5 3
1 2 2
2 4 3
4 5 2
output
3
1 3 5 

题意：

有n个点，给出m条边，每条边都有权值（可以理解为距离）。问在T距离之内，从顶点1走到顶点n，最多可以经过多少个顶点？

其中，构成的图中不会出现环，且题目至少有一个答案。

题解：

一开始以为是最短路径，很显然不是，因为题目求的不是最短路，而是在限定的起点、终点和距离的情况下，最多能经过多少个点。

然后想到应该可以用DP：

dp[len][v]：从顶点1开始，途经len个顶点（包括起点终点），终点为v所花费的最短距离。

枚举len*枚举边：在已有的dp[len-1][u]的基础上，再得出dp[len][v]，很有DP的味道。

（注：用vector存顶点之间的关系时，枚举边 = 枚举起点*枚举终点）

保存路径：

一开始是用1维数组fa[]来保存。后来发现，假设当前顶点为v，用一维存的话，存的fa[v]仅仅是路径所能达到最大时的fa[v]，而之前长度较小的路径的fa[v]会被新的fa[v]给覆盖掉。因此需要开二维数组fa[len][v]：记录在路径长度为len时，v的前一个顶点。

注意点：

if(dp[len-1][u]==INF) continue; 因为当dp[len-1][u]不合法时（其值设为2e9），如果直接把他与w（最大为1e9）相加，结果为3e9，超出了int的范围了。所以以后还是先判断其值是否合法或存在，然后再进项操作。

类似的DP：http://blog.csdn.net/dolfamingo/article/details/71024194

1.枚举长度*枚举起点*枚举终点：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ms(a, b)  memset((a), (b), sizeof(a))
 4 typedef long long LL;
 5 const int INF = 2e9;
 6 const LL LNF = 9e18;
 7 const int mod = 1e9+7;
 8 const int maxn = 5000+10;
 9 
10 struct node
11 {
12     int v, w;
13 };
14 
15 int n,m,T;
16 vector<node>G[maxn];
17 int dp[maxn][maxn], fa[maxn][maxn];
18 
19 void init()
20 {
21     scanf("%d%d%d",&n,&m,&T);
22 
23     for(int i = 1; i<=n; i++)
24         G[i].clear();
25 
26     for(int i = 1; i<=m; i++)
27     {
28         int u;
29         node e;
30         scanf("%d%d%d",&u,&e.v,&e.w);
31         G[u].push_back(e);
32     }
33 
34     ms(fa,0);
35     for(int i = 1; i<=n; i++)
36     for(int j = 1; j<=n; j++)
37         dp[i][j] = INF;
38     dp[1][1] = 0;
39 }
40 
41 void prt(int len, int u)
42 {
43     if(len>1)
44         prt(len-1, fa[len][u]);
45 
46     printf("%d ",u);
47 }
48 
49 void solve()
50 {
51     int k;
52     for(int len = 2; len<=n; len++)
53     {
54         for(int u = 1; u<n; u++)
55         {
56             for(int i = 0; i<G[u].size(); i++)
57             {
58                 int v = G[u][i].v;
59                 int w = G[u][i].w;
60 
61                 if(dp[len-1][u]==INF) continue; //少了这步，如果继续用int，会溢出，因为INF+1e9
62 
63                 int tmp = dp[len-1][u] + w;
64                 if(tmp<=T && dp[len][v]>tmp)
65                 {
66                     dp[len][v] = tmp;
67                     fa[len][v] = u;
68                 }
69             }
70         }
71         if(dp[len][n]!=INF)
72             k = len;
73     }
74 
75     printf("%d
",k);
76     prt(k,n); putchar('
');
77 
78 }
79 
80 int main()
81 {
82     init();
83     solve();
84     return 0;
85 }

View Code

2.枚举长度*枚举边：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ms(a, b)  memset((a), (b), sizeof(a))
 4 typedef long long LL;
 5 const int INF = 2e9;
 6 const LL LNF = 9e18;
 7 const int mod = 1e9+7;
 8 const int maxn = 5000+10;
 9 
10 struct node
11 {
12     int u, v, w;
13     void read()
14     {
15         scanf("%d %d %d",&u, &v, &w);
16     }
17 }edge[maxn];
18 
19 int n,m,T;
20 int dp[maxn][maxn], fa[maxn][maxn];
21 
22 void init()
23 {
24     scanf("%d%d%d",&n,&m,&T);
25     for(int i = 1; i<=m; i++)
26         edge[i].read();
27 
28     ms(fa,0);
29     for(int i = 1; i<=n; i++)
30     for(int j = 1; j<=n; j++)
31         dp[i][j] = INF;
32     dp[1][1] = 0;
33 }
34 
35 void prt(int len, int u)
36 {
37     if(len>1)
38         prt(len-1, fa[len][u]);
39 
40     printf("%d ",u);
41 }
42 
43 void solve()
44 {
45     int k;
46     for(int len = 2; len<=n; len++)
47     {
48         for(int i = 1; i<=m; i++)
49         {
50             int u = edge[i].u;
51             int v = edge[i].v;
52             int w = edge[i].w;
53 
54             if(dp[len-1][u]==INF) continue;  //少了这步，如果继续用int，会溢出，因为INF+1e9
55 
56             int cost = dp[len-1][u] + w;
57             if(cost<=T && cost<dp[len][v])
58             {
59                 dp[len][v] = cost;
60                 fa[len][v] = u;
61             }
62         }
63 
64         if(dp[len][n]!=INF)
65             k = len;
66     }
67 
68     printf("%d
",k);
69     prt(k,n); putchar('
');
70 }
71 
72 int main()
73 {
74     init();
75     solve();
76     return 0;
77 }

View Code