Journey

Journey

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

dp/记忆化搜索/拓扑排序

刚开始想到用bfs+dp，fst（然而中间有一步逻辑错了，不得不说pretest真心弱，然后rank一掉回到解放前），改正后MLE了，状态没去重存不下...

看了下其他人的，基本用的是记忆化搜索，复杂度是O（m*n）；看了下队友ac的，以为是bfs，问了下回答说是拓扑排序（不会=、=）

游少给了一种直接dp的思路Orz，复杂度是O（m*n）：

其中time[i][j]表示经过i个结点到达j结点所需要的时间，

pre[i][j]表示经过i个结点到达j结点前的结点序号。

代码如下：

 1 #include<cstdio>
 2 #include<stack>
 3 #define N 5005
 4 using namespace std;
 5 struct node{
 6     int u,v,t;
 7 }egde[N];
 8 int time[N][N],pre[N][N];
 9 int n,m,T;
10 int main(void){
11     scanf("%d%d%d",&n,&m,&T);
12     for(int i=1;i<=m;++i)
13         scanf("%d%d%d",&egde[i].u,&egde[i].v,&egde[i].t);
14     for(int i=1;i<=n;++i)
15     for(int j=1;j<=n;++j)
16         time[i][j]=T+1;
17     time[1][1]=0;
18     for(int i=1;i<n;++i)
19     for(int j=1;j<=m;++j){
20         int u=egde[j].u;
21         int v=egde[j].v;
22         int t=egde[j].t;
23         if(time[i][u]+t<time[i+1][v]){
24             time[i+1][v]=time[i][u]+t;
25             pre[i+1][v]=u;
26         }
27     }
28     int floor;
29     for(int i=n;i>=1;--i)
30     if(time[i][n]<T+1){
31         floor=i;
32         printf("%d
",floor);
33         break;
34     }
35     int nod=n;
36     stack<int>s;
37     while(pre[floor][nod]){
38         s.push(pre[floor][nod]);
39         nod=pre[floor][nod];
40         floor--;
41     }
42     while(!s.empty()){
43         nod=s.top();
44         s.pop();
45         printf("%d ",nod);
46     }
47     printf("%d
",n);
48 }