蒟蒻竟然能过一题,可能数据比较水qwq
我们选择dp
f [ i ] [ j ] f[i][j] f[i][j] 表示 在 时间 j j j 到达 i i i 点 最小的烦躁值
所以 f [ e d g e [ i ] . y ] [ e d g e [ i ] . q ] = m i n f[edge[i].y][edge[i].q]=min f[edge[i].y][edge[i].q]=min( f [ e d g e [ i ] . x ] [ j ] + v a l ( e d g e [ i ] . p − j f[edge[i].x][j]+val(edge[i].p-j f[edge[i].x][j]+val(edge[i].p−j ) )
记得按结束时间排序,不然会出现继承问题
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn = 4001;
const int INF = 2147483647;
const int maxtime = 1001;
struct node
{
int from,to,next,st,en;
}edge[2*maxn];
int cnt;
int n,m,a,b,c;
long long f[maxn][maxtime];
int tmax = -INF;
void add(int from,int to,int st,int en)
{
edge[++cnt].to=to;
edge[cnt].from=from;
edge[cnt].st=st;
edge[cnt].en=en;
}
bool cmp1(node a,node b){return a.en<b.en;}
int val(int x){return a*x*x+b*x+c;}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
memset(f,-1,sizeof(f));
for(int i=1;i<=m;i++)
{
int x,y,st,en;
scanf("%d%d%d%d",&x,&y,&st,&en);
if(x==1)
f[y][en]=val(st);
else add(x,y,st,en);
tmax=max(tmax,en);
}
sort(edge+1,edge+1+cnt,cmp1);
for(int i=1;i<=m;i++)
{
int from=edge[i].from,to=edge[i].to,st=edge[i].st,en=edge[i].en;
for(int j=1;j<=st;j++)
{
if(f[from][j]!=-1)
{
if(f[to][en]!=-1)f[to][en]=min(f[to][en],f[from][j]+val(st-j));
else f[to][en]=f[from][j]+val(st-j);
}
}
}
int ans=INF;
for(int i=1;i<=tmax;i++)
{
if(f[n][i]!=-1)
ans=min(ans,f[n][i]+i);
}
cout<<ans;
}
最后
以上就是优雅中心最近收集整理的关于洛谷P5468(DP)回家路线的全部内容,更多相关洛谷P5468(DP)回家路线内容请搜索靠谱客的其他文章。
发表评论 取消回复