Journey

题目链接：

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
     
       2 #include
      
        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
       
        =1;--i)30     if(time[i][n]
        

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",n);48 }