首页 > 代码库 > Codeforces Round #374 (Div. 2) C. Journey
Codeforces Round #374 (Div. 2) C. Journey
题解:
dfs+dp
dp[i][j]表示经过i个点后到达j点的最小花费
在dfs每个点的过程中加个for循环i
注意用 long long MLE
代码:
#include<bits/stdc++.h> #define maxn 5010 #define mod 1000000007 #define ll long long #define pb push_back using namespace std; const int INF=1e9+7; struct Edge { int v,nxt,t; }edge[maxn]; int head[maxn],pre[maxn][maxn],vis[maxn]; int dp[maxn][maxn]; int cnt,sum,n,m,T; void init() { memset(head,-1,sizeof(head)); cnt=0; for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) dp[i][j]=INF; memset(pre,-1,sizeof(pre)); } void addedge(int u,int v,int t) { edge[cnt].v=v; edge[cnt].t=t; edge[cnt].nxt=head[u]; head[u]=cnt++; } void dfs(int u) { if(vis[u]) return; vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].nxt) { int v=edge[i].v,t=edge[i].t; dfs(v); for(int i=2;i<=n;i++) { ll dis=dp[v][i-1]+t; if(dis<dp[u][i]) { dp[u][i]=dis; pre[u][i]=v; } } } } void print_path() { for(int i=n;i>=0;i--) { if(dp[1][i]<=T) { printf("%d\n",i); int x=1; printf("%d ",x); while(i>1) { x=pre[x][i--]; printf("%d ",x); } break; } } } int main() { init(); scanf("%d%d%d",&n,&m,&T); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } dp[n][1]=0; vis[n]=1; dfs(1); print_path(); }
Codeforces Round #374 (Div. 2) C. Journey
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。