想写一个 70 pts 算法,结果数据水,直接就切了
最短路:
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; #define setIO(s) freopen(s".in","r",stdin) #define maxn 300000 #define ll long long struct Node { int x,y,p,q; }nd[maxn]; vector<int>G1[maxn],G2[maxn]; map<int,int>date1[maxn],date2[maxn]; int n,m,A,B,C,cnt1,edges,cnt2; int hd[maxn*10],to[maxn*10],nex[maxn*10]; ll val[maxn*10]; inline void addedge(int u,int v,ll c) { nex[++edges]=hd[u], hd[u]=edges, to[edges]=v,val[edges]=c; } inline ll calc(ll u) { return 1ll*A*u*u + 1ll*B*u + 1ll*C; } int S,T; int inq[maxn*10]; ll dis[maxn*10]; queue<int>Q; inline void spfa() { for(int i=1;i<maxn*10;++i) dis[i]=1000000000000; Q.push(S); inq[S]=1; dis[S]=0; while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for(int i=hd[u];i;i=nex[i]) { int v=to[i]; if(dis[u]+val[i] < dis[v]) { dis[v]=dis[u] + val[i]; if(!inq[v]) { inq[v]=1; Q.push(v); } } } } printf("%lld\n",dis[T]); } int main() { int i,j; // setIO("input"); scanf("%d%d%d%d%d",&n,&m,&A,&B,&C); for(i=1;i<=m;++i) { scanf("%d%d%d%d",&nd[i].x,&nd[i].y,&nd[i].p,&nd[i].q); G1[nd[i].y].push_back(nd[i].q); G2[nd[i].x].push_back(nd[i].p); if(!date2[nd[i].x][nd[i].p]) date2[nd[i].x][nd[i].p]=++cnt2; if(!date1[nd[i].y][nd[i].q]) date1[nd[i].y][nd[i].q]=++cnt1; } for(i=1;i<=m;++i) { addedge(date2[nd[i].x][nd[i].p], date1[nd[i].y][nd[i].q] + cnt2, 0); } int k=0; for(i=1;i<=n;++i) { if(!G1[i].size() || !G2[i].size()) continue; for(j=0;j<G1[i].size();++j) { for(k=0;k<G2[i].size();++k) { if(G1[i][j]>G2[i][k]) continue; addedge(date1[i][G1[i][j]] + cnt2, date2[i][G2[i][k]], calc(G2[i][k] - G1[i][j])); } } } S=0,T=cnt1 + cnt2 +100; for(i=0;i<=1000;++i) if(date2[1][i]) addedge(S, date2[1][i], calc(i)); for(i=0;i<=1000;++i) if(date1[n][i]) addedge(date1[n][i] + cnt2, T, i); spfa(); return 0; }
$O(mt)$ DP (网上说这个做法在现场能切题)
#include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 300001 #define inf 1000000000 using namespace std; int n,m,A,B,C; int f[maxn][1002]; int calc(int t) { return A*t*t+B*t+C; } struct Node{ int x,y,p,q; }nd[maxn]; bool cmp(Node a, Node b) { return a.p < b.p; } int main() { // setIO("input"); int i,j; scanf("%d%d%d%d%d",&n,&m,&A,&B,&C); for(i=1;i<=m;++i) { scanf("%d%d%d%d",&nd[i].x,&nd[i].y,&nd[i].p,&nd[i].q); } sort(nd+1,nd+1+m,cmp); for(i=0;i<=n;++i) for(j=0;j<=1000;++j) f[i][j]=inf; f[1][0]=0; for(i=1;i<=m;++i) { for(j=0;j<=nd[i].p;++j) { if(f[nd[i].x][j]==inf) continue; f[nd[i].y][nd[i].q] = min(f[nd[i].y][nd[i].q], f[nd[i].x][j] + calc(nd[i].p - j)); } } int ans=inf; for(i=0;i<=1000;++i) { ans=min(ans, f[n][i] + i); } printf("%d\n",ans); return 0; }