BZOJ 1003: [ZJOI2006]物流运输 [DP+ 最短路]

本文主要是介绍BZOJ 1003: [ZJOI2006]物流运输 [DP+ 最短路]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Time Limit: 10 Sec   Memory Limit: 162 MB
Submit: 9148   Solved: 3952
[ Submit][ Status][ Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

[思路]

    对于条件分析， 很容易发现 就是 DP 问题，  然而 如何DP，   愁啊

    对天数有限制， 那么  就得从天数 下手，

    DP[i] 代表 到第i 天是 最小花费;  那么 DP[i]  与 前面某一天j话费 加上从i-j 变道需要的话费 有关

    cost[i][j] 代表从 i-j 的最小开销 则 DP[i] = min(DP[i],DP[j}+(i-j)*cost[i][j] +k)

    每次标记 不能走的地方，  跑SPFA  N^2 

[代码实现]

#include <iostream>
#include <bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;using namespace std;int head[MAXN];
int dis[MAXN],vis[MAXN],flag[MAXN];
int dp[MAXN];
int a[505][505];
int cost[505][505];
int n,k,e,m,d,cot;struct node{int v,w,next;
}edge[MAXN];void init()
{cot=0;mem(head,-1);
}
void add(int u,int v,int w)
{edge[++cot].v=v;edge[cot].w=w;edge[cot].next=head[u];head[u]=cot;
}
int spfa(int s)
{queue<int>Q;mem(dis,INF);dis[s]=0;vis[s]=1;Q.push(s);while(!Q.empty()){int u=Q.front();Q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;int w=edge[i].w;if(!flag[v]&& dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){Q.push(v);vis[v]=1;}}}}return dis[m];
}
int main()
{cin>>n>>m>>k>>e;init();mem(a,0);int x,y,z;for(int i=1;i<=e;i++){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}cin>>d;for(int i=1;i<=d;i++){cin>>z>>x>>y;for(int k=x;k<=y;k++)a[z][k]=1;}for(int i=1;i<=n;i++){mem(flag,0);for(int j=i;j<=n;j++){for(int k=1;k<=m;k++)flag[k]+=a[k][j];cost[i][j]=spfa(1);}}mem(dp,INF);dp[0]=-k;for(int i=1;i<=n;i++){for(int j=0;j<=i;j++){if(cost[j+1][i]!=INF)dp[i]=min(dp[i],dp[j]+k+cost[j+1][i]*(i-j));}}cout<<dp[n]<<endl;return 0;
}

这篇关于BZOJ 1003: [ZJOI2006]物流运输 [DP+ 最短路]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---