codeforces 721 C jurney(動的企画+トポロジカル順序)
2247 ワード
試合の時は書かれていませんでしたが、ネット上の大牛のブログを見てやっと分かりました.この問題を通じて前の星や位相順が分かりました.
大牛のブログ:http://www.cnblogs.com/ziliuziliu/p/5931553.html
自分のコードを添付して、コメントがあります.
大牛のブログ:http://www.cnblogs.com/ziliuziliu/p/5931553.html
自分のコードを添付して、コメントがあります.
#include
#define INF 0x3f3f3f3f
using namespace std;
int n,m,t,head[5005],cnt,dp[5005][5005],pre[5005][5005],d[5005],path[5005]; //dp[i][j] j ( i ) i
struct node
{
int to; //
int next; //
int w; //
}edge[5005];
void add(int x,int y,int z) //
{
edge[cnt].to=y;
edge[cnt].next=head[x];
edge[cnt].w=z;
head[x]=cnt++;
}
queueq;
void bfs() //
{
dp[1][1]=0;
bool visit[5005];
for(int i=1;i<=n;i++)
{
if(!d[i])
{
visit[i]=true;
q.push(i);
}
}
while(!q.empty()) //bfs
{
int top=q.front();
q.pop();
for(int i=head[top];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(d[v])
{
d[v]--;
for(int j=2;j<=n;j++)
{
if(dp[v][j]>dp[top][j-1]+edge[i].w)
{
dp[v][j]=dp[top][j-1]+edge[i].w;
pre[v][j]=top; // , v , 1 v , j-1
}
}
}
if(!d[v]) q.push(v); // d[v] 0, v , v
}
}
}
int main()
{
int a,b,c,max1=0,num=0,x;
memset(head,-1,sizeof(head));
cnt=0;
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
d[b]++;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=INF;
}
}
bfs();
for(int i=n;i>=1;i--)
{
if(dp[n][i]<=t) // n , t ,
{
max1=i;
break;
}
}
printf("%d
",max1);
x=n;
while(x!=1) //
{
path[++num]=x;
x=pre[x][max1];
max1--;
}
path[++num]=1;
for(int i=num;i>=1;i--)
printf("%d ",path[i]);
return 0;
}