WA #63 RE
  • 板块CF721C Journey
  • 楼主Kniqht
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/3 18:26
  • 上次更新2023/12/3 20:48:06
查看原帖
WA #63 RE
315205
Kniqht楼主2023/12/3 18:26

过了62个点你告诉我第63个RE了?但我觉得数组大小没问题啊

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fir first
#define sec second
using namespace std;
const int N=5010;
int n,m,k; 
int d[N];
int h[N],e[N*2],w[N*2],ne[N*2],idx;
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
	d[b]++;
}
int f[N][N];
int fa[N][N];
queue<int> q;
void topsort(){
	q.push(1);f[1][1]=0;
	while(!q.empty()){
		int t=q.front();q.pop();
		for(int i=h[t];~i;i=ne[i]){
			int j=e[i];
			for(int c=2;c<=n;c++)
				if(f[t][c-1]+w[i]<f[j][c]&&f[t][c-1]+w[i]<=k) 
					fa[j][c]=t,f[j][c]=f[t][c-1]+w[i];
			if(--d[j]==0) q.push(j);
		}
	}
}
// f(i,j) 代表从 1->i,经过 j 点数最少边权
void print(int x,int y){
	if(x!=1) print(fa[x][y],y-1);
	printf("%d ",x);
} 
signed main(){
	memset(f,0x3f,sizeof(f));
	memset(h,-1,sizeof(h));
	scanf("%d%d%d",&n,&m,&k);
	int u,v,w;
	while(m--){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}topsort();
	int ans=0;PII t;
	for(int i=1;i<=n;i++)
		if(f[n][i]<=k&&i>ans){
			ans=i;
			t={n,i};
		}
	printf("%d\n",ans);print(t.fir,t.sec);
	return 0;
}
2023/12/3 18:26
加载中...