[关闭]
@zzzc18 2017-05-11T03:44:32.000000Z 字数 1598 阅读 589

bzoj 1003

bzoj


题目

Solution

首先要预处理出对于任意的 i<=j<=day 第i到j天的最短路//这里存放在cost中

然后用动态规划来解决所有天数里可行的的最小值

状态转移方程

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define MAXM 1100
  6. using namespace std;
  7. int day,n,K,m,tot;
  8. struct E{
  9. int next,to,val;
  10. }edge[MAXM];
  11. int head[MAXM],edge_num;
  12. int block[MAXM][MAXM];
  13. int mark[MAXM];
  14. int cost[MAXM][MAXM];
  15. int dis[MAXM],inque[MAXM];
  16. queue<int> que;
  17. int dp[MAXM];
  18. int inf;
  19. void addedge(int x,int y,int z){
  20. edge[++edge_num].next=head[x];
  21. edge[edge_num].to=y;
  22. edge[edge_num].val=z;
  23. head[x]=edge_num;
  24. }
  25. int SPFA(){
  26. memset(dis,0x7f,sizeof(dis));
  27. inf=dis[0];
  28. inque[1]=1;
  29. dis[1]=0;
  30. que.push(1);
  31. while(!que.empty()){
  32. int fro=que.front();que.pop();inque[fro]=0;
  33. int i;
  34. for(i=head[fro];i;i=edge[i].next){
  35. if(dis[edge[i].to]>dis[fro]+edge[i].val && !mark[edge[i].to]){
  36. dis[edge[i].to]=dis[fro]+edge[i].val;
  37. if(!inque[edge[i].to]){
  38. que.push(edge[i].to);
  39. inque[edge[i].to]=1;
  40. }
  41. }
  42. }
  43. }
  44. return dis[n];
  45. }
  46. int DP(){
  47. int i,j;
  48. for(i=1;i<=day;i++)
  49. dp[i]=cost[1][i];
  50. for(i=2;i<=day;i++){
  51. for(j=1;j<i;j++){
  52. dp[i]=min(dp[j]+cost[j+1][i]+K,dp[i]);
  53. }
  54. }
  55. return dp[day];
  56. }
  57. void solve(){
  58. int i,j,k,l;
  59. for(i=1;i<=day;i++){
  60. for(j=i;j<=day;j++){
  61. memset(mark,0,sizeof(mark));
  62. for(k=1;k<=n;k++){
  63. for(l=i;l<=j;l++){
  64. mark[k]|=block[k][l];
  65. }
  66. }
  67. cost[i][j]=SPFA();
  68. }
  69. }
  70. for(i=1;i<=day;i++){
  71. for(j=i;j<=day;j++){
  72. if(cost[i][j]!=inf)
  73. cost[i][j]*=(j-i+1);
  74. }
  75. }
  76. printf("%d\n",DP());
  77. }
  78. int main(){
  79. freopen("bz.in","r",stdin);
  80. scanf("%d%d%d%d",&day,&n,&K,&m);
  81. int i;
  82. for(i=1;i<=m;i++){
  83. int a,b,c;
  84. scanf("%d%d%d",&a,&b,&c);
  85. addedge(a,b,c);
  86. addedge(b,a,c);
  87. }
  88. scanf("%d",&tot);
  89. for(i=1;i<=tot;i++){
  90. int a,b,c;
  91. scanf("%d%d%d",&a,&b,&c);
  92. for(int j=b;j<=c;j++)
  93. block[a][j]=1;
  94. }
  95. solve();
  96. return 0;
  97. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注