Codeforces 721 C. Journey（拓扑排序+DP）
codeforces每日一练。
题意:
给定n个点，m条有向边，以及k时间。求不超过k时间1-n最多能经过多少个点。
思路：
数据<=5000，说明是个暴力dp。 那么可以用dp[i][j]维护从1到i点经过了j个点，然后初始化为inf，再设dp[1][1]=0，保证每个dp都是由1出发的。 因为是有向无环图，所以我们可以在拓扑排序的时候进行dp，循环n个点，复杂度On^2，然后多开一个pre[i][j]记录经过i点时的前一个点。 由于开了两个5000*5000的数组，所以得用int，如果用long long会MLE。代码如下：
#include
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define ins insert
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#pragma GCC optimize(2)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch>= 1;}return ans%p;}ll Inv(ll x,ll p){return qp(x,p-2,p);}
ll Cal(ll n,ll m,ll p){if (m>n) return 0;ll ans = 1;for(int i = 1; i <= m; ++i)
ans=ans*Inv(i,p)%p*(n-i+1)%p;return ans%p;}
const int manx=5e3+5;
struct node{
int v,next,w;
}a[manx];
queueq;
int head[manx],kk=0;
int d[manx],dp[manx][manx],pre[manx][manx];
void add(int u,int v,int w){
a[++kk].v=v,a[kk].w=w,a[kk].next=head[u],head[u]=kk;
}
int main(){
int n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
add(u,v,w);
++d[v];
}
for(int i=1;i<=n;i++)
if(!d[i]) q.push(i);
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
dp[i][j]=inf;
dp[1][1]=0;
while(q.si){
int u=q.front(); q.pop();
for(int x=head[u];x;x=a[x].next){
int v=a[x].v,w=a[x].w;
for(int i=1;idp[u][i-1]+w)
dp[v][i]=dp[u][i-1]+w,pre[v][i]=u;
--d[v];
if(!d[v]) q.push(v);
}
}
int tmp=0,x=n;
for(int i=n;i>=1;i--)
if(dp[n][i]=1;i--) d[++top]=n,n=pre[n][i];
while(top) printf("%d ",d[top--]);
return 0;
}
作者：别对自己失望
