<span>codeforces721C Journey（dp暴力）</span>
题意：
5000个点5000条边的图，总长为t（1e9）
每条边都有边长（1e9）
问你从1到n走的路程不超过总长的条件下经过节点数最多的方案输出任意路径
思路：
5000*5000暴力
最多答案就是n，dp[i][j]代表经过了i个节点到达了节点j的最小距离
每一层对所有的边更新，记一下前驱
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <time.h> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=5e3+10; int d[N][N],mp[N][3],pre[N][N],show[N],n,m,v,ans,l; int main() { #ifndef ONLINE_JUDGE //IN #endif scanf("%d%d%d",&n,&m,&v); memset(d,inf,sizeof(d)); for(int i=1;i<=m;i++) for(int j=0;j<=2;j++) scanf("%d",&mp[i][j]); d[1][1]=0; for(int i=2;i<=n;i++) for(int j=1;j<=m;j++) { if(d[i-1][mp[j][0]]+mp[j][2]<d[i][mp[j][1]]&&d[i-1][mp[j][0]]+mp[j][2]<=v) { d[i][mp[j][1]]=d[i-1][mp[j][0]]+mp[j][2]; pre[i][mp[j][1]]=mp[j][0]; } if(d[i][n]<=v) ans=i; } printf("%d\n",ans); for(int j=n;j;j=pre[ans--][j]) show[++l]=j; for(int i=l;i>=1;i--) printf("%d ",show[i]); return 0; }
查看3道真题和解析
