BZOJ 1003 物流运输trans dijstra+dp

题目链接:

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跑一发

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 9999999;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e2+10;
17 
18 int n,m,k,e;
19 int flag[maxn][maxn],f[maxn],d[maxn],dp[maxn];
20 vector<pair<int,int> > G[maxn];
21 
22 int cost(int s,int e){
23     MS(f); 
24     for(int i=1;i<=m;i++)
25         d[i]=INF;
26 
27     for(int i=1; i<=m; i++){
28         for(int j=s; j<=e; j++)
29             if(flag[i][j])
30                 f[i] = 1;
31     }
32 
33     queue<int> q;
34     d[1] = 0;
35     q.push(1);
36     while(!q.empty()){
37         int u = q.front(); q.pop();
38         for(int i=0; i<(int)G[u].size(); i++){
39             pair<int,int> p = G[u][i];
40             int v = p.first, w = p.second;
41             if(f[v]) continue;
42             if(d[v] > d[u]+w){
43                 d[v] = d[u]+w;
44                 q.push(v);
45             }
46         }
47     }
48     // cout << d[m] << "  pp
";
49     int ans = d[m]*(e-s+1);
50     return ans;
51 }
52 
53 int main(){
54     scanf("%d%d%d%d",&n,&m,&k,&e);
55     for(int i=0; i<e; i++){
56         int u,v,w; scanf("%d%d%d",&u,&v,&w);
57         G[u].push_back(MP(v,w));
58         G[v].push_back(MP(u,w));
59     }
60 
61     int d = read();
62     for(int i=0; i<d; i++){
63         int u,ii,jj;
64         scanf("%d%d%d",&u,&ii,&jj);
65         for(int j=ii; j<=jj; j++)
66             flag[u][j] = 1;
67     }
68     // cout << "hh
";
69     for(int i=1; i<=n; i++){
70         dp[i] = cost(1,i);
71         // cout << dp[i] << "  kk
";
72         for(int j=1; j<i; j++)
73             dp[i] = min(dp[i],dp[j]+cost(j+1,i)+k);
74     }
75 
76     cout << dp[n] << endl;
77 
78     return 0;
79 }