codeforces 721C (拓扑+dp)

题意就是某个人去游览，起点是1点，终点是n点，他总的游览时间不能超过t，第一行给你3个数字，点的个数n，边的个数m,时间t，然后底下m行数据，每行代表一条边，边的起点，终点和权值（走过去花的时间），然后问你，她想尽量多的游览景点，还要求总时间不能超过t（他在景点不会逗留，所以只要计算路程花费的时间即可），问你怎么走，输出路径

题目我不会做，看了题解，dalao的思路的拓扑+dp，直接dp貌似不行，为什么用拓扑+dp呢- -，我感觉里面就是让你求最长的哈密顿路径- -，这就很哲学了- -，看了dalao的代码，给dalao的代码加点注释，方便以后自己查看

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#include <map>
using namespace std;
const int Maxn = 5e3+100;
const int INF = 0x3f3f3f3f;

struct Node{//构造函数
    int to;
    int dis;
    Node(){}
    Node(int a,int b){
        to = a;
        dis = b;
    }
};

int dp[Maxn][Maxn];
std::vector<Node> G[Maxn];
std::queue<int> q;
std::map<int,int> du;
int ans[Maxn];
int pre[Maxn][Maxn];




int main(){
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    memset( dp,INF,sizeof( dp ) );//初始化为无穷大
    int Begin,End,w;
    for( int i = 1; i <= m; i++ ){
        scanf("%d%d%d",&Begin,&End,&w);
        G[Begin].push_back( Node( End,w ) );//将与之begin相邻的点放在vector里
        du[End]++;//End点的入度+1   为下面拓扑排序做准备
    }
    dp[1][1] = 0;
    for( int i = 1; i <= n; i++ ){//将入度为0的点压入队列中（kahn算法拓扑排序）
        if( !du[i] ){
            q.push(i);
        }
    }
    while( !q.empty() ){
        int i = q.front();
        q.pop();
        for( auto x : G[i] ){//取出所有的与i点为起点的点（即处理i线段）
            Node tmp = x;
            if( !--du[tmp.to] ){//将i点的那条线段的终点入度减一，如果为0，压入队列（kahn算法）
                q.push(tmp.to);
            }
            for( int k = 2; k <= n; k++ ){//起点必须为1点，所以从2开始
                if( dp[i][k-1] + tmp.dis < dp[tmp.to][k] ){//dp[i][j]代表从1到i点，经历了j条边的权值总和
                    dp[tmp.to][k] = dp[i][k-1] + tmp.dis;//如果1到i经历了k-1条边+从i到i.to那条边的和小于从1到i经历了k条边
                    pre[tmp.to][k] = i;//就更新一下值（尽量选大的）
                    //记录下父亲节点
                }
            }
        }
    }
    int num;
    for( int i = n; i >= 1; i-- ){
        if( dp[n][i] <= t ){//找到第一个满足条件的点
            num = i;
            break;
        }
    }
    ans[num] = n;//终点为n
    for( int i = n,j = num; j > 1; i = pre[i][j],j-- ){
        ans[j-1] = pre[i][j];//记录下路径
    }
    printf("%d\n",num);
    for( int i = 1; i <= num; i++ ){
        printf("%d ",ans[i]);
    }
    return 0;
}