首页 > 代码库 > CF721C. Journey

CF721C. Journey

2024-08-15 09:23:41   211人阅读

传送门

说实话，这是一道非常简单的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 }
View Code

 

CF721C. Journey


联系
我们