【ZJOI2006】物流运输

题面

https://www.luogu.org/problem/P1772

题解

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define LL long long
#define ri register int
#define N 105
#define INF 100000000000000007LL

using namespace std;

int n,m,k,e;
int d[N][N];
LL f[N];
LL dis[N];
bool vis[N],used[N][N];

LL min(LL a,LL b) {
  if (a<b) return a; else return b;
}

LL dij(int l,int r) {
  bool cant[N];
  memset(cant,0,sizeof(cant));
  
  for (ri i=l;i<=r;i++) 
    for (ri j=1;j<=m;j++) if (used[i][j]) cant[j]=1;

  memset(dis,0x3f,sizeof(dis));
  memset(vis,0,sizeof(vis));
  
  dis[1]=0;vis[1]=1;
  for (ri i=1;i<=m;i++) if (!cant[i]) dis[i]=min(dis[i],d[1][i]);
  
  for (ri i=2;i<=m;i++) {
    int p=-1; LL mind=INF;
    for (ri j=1;j<=m;j++) if (!cant[j] && !vis[j] && dis[j]<mind) mind=dis[j],p=j;
    if (p==-1) break;
    vis[p]=1;
    for (ri j=1;j<=m;j++) if (!cant[j] && dis[p]+d[p][j]<dis[j]) dis[j]=dis[p]+d[p][j];
  }
  
  if (dis[m]>INF) return INF;
  return dis[m];
}
int main(){
  int yourd,a,b,c;
  scanf("%d %d %d %d",&n,&m,&k,&e);
  memset(d,0x3f,sizeof(d));
  for (ri i=1;i<=e;i++) {
    scanf("%d %d %d",&a,&b,&c);
    d[a][b]=d[b][a]=min(d[a][b],c);
  }
  scanf("%d",&yourd);
  for (ri i=1;i<=yourd;i++) {
    scanf("%d %d %d",&a,&b,&c);
    for (ri i=b;i<=c;i++) used[i][a]=1;
  }
  memset(f,0x3f,sizeof(f));
  f[0]=-k;
  for (ri i=1;i<=n;i++) 
    for (ri j=0;j<i;j++) f[i]=min(f[i],f[j]+(i-j)*dij(j+1,i)+k);
  cout<<f[n]<<endl;
  return 0;
}