codeforces 721 C(トポロジー+DP)

タイトルリンク:http://codeforces.com/contest/721/problem/C
标题:1からnまで歩いて、時間T内で最大何点を通過するかを聞いて、パス順に出力します.
考え方:試合の時は拓排のことしか考えていなかったので、どうしたらいいか分からなかったのですが...まずトポロジーソートを行い,さらにトポロジー順にDPを行い,dp[to][j](i点までj点を通過する最短時間)=min(dp[to][j],dp[i][j]+dis)

#include
using namespace std;
typedef long long ll;
const int N = 5e3 + 3;
const int inf = 0x3f3f3f3f;
struct node
{
    int to;
    int dis;
    node() {}
    node(int a,int b) : to(a), dis(b) {}
};
vector  G[N];
queue q;
int dp[N][N],pre[N][N],ans[N],deg[N];
int main()
{
    int n,m,t,num;
    scanf("%d %d %d",&n,&m,&t);
    memset(dp,inf,sizeof(dp));
    for(int i = 1; i <= m; i++)
    {
        int u,v,d;
        scanf("%d %d %d",&u,&v,&d);
        G[u].push_back(node(v,d));
        deg[v]++;
    }
    dp[1][1] = 0;
    for(int i = 1; i <= n; i++)
    {
        if(!deg[i])
            q.push(i);
    }
    while(!q.empty())
    {
        int i = q.front();
        q.pop();
        for(int j = 0; j < G[i].size(); j++)
        {
            node tmp = G[i][j];
            if(!--deg[tmp.to])
                q.push(tmp.to);
            for(int k = 2; k <= n; k++)
            {
                if(dp[i][k-1] + tmp.dis < dp[tmp.to][k])
                {
                    dp[tmp.to][k] = dp[i][k-1] + tmp.dis;
                    pre[tmp.to][k] = i;
                }
            }
        }
    }
    for(int i = n; i >= 1; i--)
    {
        if(dp[n][i] <= t)
        {
            num = i;
            break;
        }
    }
    ans[num] = n;
    for(int i = n,j = num; j > 1; i = pre[i][j], j--)
       ans[j-1] = pre[i][j];
    printf("%d
",num);
    for(int i = 1; i <= num; i++)
        printf("%d ",ans[i]);
    return 0;
}

 
 
転載先:https://www.cnblogs.com/westwind1005/p/5975182.html