codeforces 721C

题意：一个n个点，m条边的无环无重边有向图，经过第i条路径需花费时间ti，要求你选一条从1到n的路径，使得经过的不同城市最多，并且总时间小于等于t。

 

 

 

题解：很简单的一道dp，考试的时候没想出来，一通乱搞，最后跑去A了D题。

dp[i][j]表示第i个点，已经经过了j个点的最小时间，按照拓扑序搞一搞即可。

#include<bits/stdc++.h>
#define maxn 5005
#define inf 2000000000
using namespace std;
int dp[maxn][maxn],fr[maxn][maxn],cnt,n,m,t,head[maxn],tup[maxn],q[maxn],num;
struct edge{int to,next,v;}e[2*maxn];
void ins(int u,int v,int val){
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=val;
}
void dfs(int k){
    for(int i=head[k];i;i=e[i].next){
        tup[e[i].to]--;
        for(int j=1;j<=n;j++){
            if(dp[k][j]<=t&&dp[e[i].to][j+1]>dp[k][j]+e[i].v) {
                dp[e[i].to][j+1]=dp[k][j]+e[i].v;
                fr[e[i].to][j]=k;
            }
        }
        if(tup[e[i].to]==0) dfs(e[i].to);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&t);int a,b,c;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        ins(a,b,c);
        tup[b]++;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) dp[i][j]=t+1;
    dp[1][1]=0;
    for(int i=1;i<=n;i++){
        if(tup[i]==0){
            dfs(i);
        }
    }dp[n][0]=0;
    for(int i=n;i>=0;i--){
        if(dp[n][i]<=t){
            printf("%d\n",i);num=i;
            for(int poi=n;poi!=1;poi=fr[poi][num]){
                q[num]=poi;num--;
            }
            num=i;
            break;
        }
    }printf("1");
    for(int i=2;i<=num;i++) printf(" %d",q[i]);printf("\n");
    return 0;
}