以前版刷BZOJ的时候见过这道题来着 然后没看懂
现在还是绕不开了
意思是给你一个图,有一些点在某些时间段不能走,每个时间点要有一条从1到m的路径,产生路径长度的代价,并且每个时间点将路径变更的代价为K。求最小代价和。
看到数据范围很小,首先枚举时间端点l、r,预处理[l,r]不变更路径的最小代价。然后就可以随意dp了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// <1003.cpp> - 05/14/16 17:41:26 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <queue> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=110; const int INF=1e7; int bt,b[MAXN],next[1001],to[1001],val[1001]; inline void add(int v,int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=v; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=v; } bool ban[MAXN][MAXN],ded[MAXN]; int sum[MAXN][MAXN]; int n,m,dis[MAXN]; queue <int> q; bool in[MAXN]; inline int spfa(){ for(int i=2;i<=m;i++)dis[i]=INF; q.push(1);in[1]=1; while(!q.empty()){ int now=q.front();q.pop();in[now]=0; for(int i=b[now];i;i=next[i]) if(!ded[to[i]]&&dis[now]+val[i]<dis[to[i]]){ dis[to[i]]=dis[now]+val[i]; if(!in[to[i]]){q.push(to[i]);in[to[i]]=1;} } } return dis[m]; } int dp[MAXN]; int main(){ n=gi(),m=gi(); int K=gi(),e=gi(); for(int i=1;i<=e;i++)add(gi(),gi(),gi()); int d=gi(); while(d--){ int g=gi(),l=gi(),r=gi(); for(int i=l;i<=r;i++)ban[g][i]=1; } for(int l=1;l<=n;l++) for(int r=l;r<=n;r++){ for(int i=2;i<m;i++){ ded[i]=0; for(int j=l;j<=r;j++) if(ban[i][j]){ded[i]=1;break;} } sum[l][r]=spfa(); } for(int i=1;i<=n;i++){ dp[i]=i*sum[1][i]; for(int j=1;j<i;j++)dp[i]=min(dp[i],dp[j]+K+(i-j)*sum[j+1][i]); } printf("%d",dp[n]); return 0; } |