BZOJ 1003 物流运输trans dijstra+dp

2019-11-06 07:53:13

字体：大中小

来源：转载

供稿：网友

题目链接:

http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1003

题意:

题解:

首先我们必须机智的知道f[i]=min(f[i],f[j]+cost(j+1,i)+k)这个dp方程 cost(i,j)表示从第i天到第j天的最小花费 dijstra跑一发

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 9999999;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 1e2+10;int n,m,k,e;int flag[maxn][maxn],f[maxn],d[maxn],dp[maxn];vector<pair<int,int> > G[maxn];int cost(int s,int e){ MS(f); for(int i=1;i<=m;i++) d[i]=INF; for(int i=1; i<=m; i++){ for(int j=s; j<=e; j++) if(flag[i][j]) f[i] = 1; } queue<int> q; d[1] = 0; q.push(1); while(!q.empty()){ int u = q.front(); q.pop(); for(int i=0; i<(int)G[u].size(); i++){ pair<int,int> p = G[u][i]; int v = p.first, w = p.second; if(f[v]) continue; if(d[v] > d[u]+w){ d[v] = d[u]+w; q.push(v); } } } // cout << d[m] << " pp/n"; int ans = d[m]*(e-s+1); return ans;}int main(){ scanf("%d%d%d%d",&n,&m,&k,&e); for(int i=0; i<e; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); G[u].push_back(MP(v,w)); G[v].push_back(MP(u,w)); } int d = read(); for(int i=0; i<d; i++){ int u,ii,jj; scanf("%d%d%d",&u,&ii,&jj); for(int j=ii; j<=jj; j++) flag[u][j] = 1; } // cout << "hh/n"; for(int i=1; i<=n; i++){ dp[i] = cost(1,i); // cout << dp[i] << " kk/n"; for(int j=1; j<i; j++) dp[i] = min(dp[i],dp[j]+cost(j+1,i)+k); } cout << dp[n] << endl; return 0;}

上一篇：IO流_Properties的概述和作为Map集合的使用

下一篇：跳台阶

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注