首页 > 代码库 > CF721C. Journey
CF721C. Journey
传送门
说实话,这是一道非常简单的DP题,简单到如果放到NOIp第二题可能都有些差强人意,然而我写崩了。
所以简单记录一下。
需要注意的是,这道题的DP应该是从$N$点开始,以1为边界,满足最短路的三角形性质即可转移。
1 //cf c 2 //by Cydiater 3 //2016.9.30 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <cstdlib>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int MAXN=1e6+5;20 const int oo=0x3f3f3f3f;21 inline ll read(){22 char ch=getchar();ll x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 int LINK[MAXN],len=0,N,M,T,ans=0,lastnode[MAXN],q[MAXN],top=0;28 bool vis[MAXN];29 ll f[5005][5005];30 struct edge{31 int y,next;ll v;32 }e[MAXN];33 namespace solution{34 inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}35 void init(){36 N=read();M=read();T=read();37 up(i,1,M){38 ll x=read(),y=read(),v=read();39 insert(y,x,v);40 }41 }42 void dfs(int node){43 if(vis[node])return;44 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y])dfs(e[i].y);45 for(int i=LINK[node];i;i=e[i].next)if(e[i].v>0)46 up(j,1,N)if(f[e[i].y][j-1]+e[i].v<f[node][j]){47 f[node][j]=f[e[i].y][j-1]+e[i].v;48 if(node==N&&f[node][j]<=T)ans=max(ans,j);49 }50 vis[node]=1;51 }52 void re_dfs(int node,int num){53 for(int i=LINK[node];i;i=e[i].next)if(num>0){54 if(f[e[i].y][num-1]==f[node][num]-e[i].v){55 lastnode[node]=e[i].y;56 re_dfs(e[i].y,num-1);57 return;58 }59 }60 }61 void DP(){62 memset(f,10,sizeof(f));63 f[1][1]=0;64 dfs(N);65 }66 void output(){67 cout<<ans<<endl;68 if(ans==0)return;69 re_dfs(N,ans);70 for(int i=N;i!=0;i=lastnode[i])q[++top]=i;71 down(i,top,1)printf("%d ",q[i]);72 puts("");73 }74 }75 int main(){76 //freopen("input.in","r",stdin);77 using namespace solution;78 init();79 DP();80 output();81 return 0;82 }
CF721C. Journey
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。