P1772 [ZJOI2006]物流运输-白红宇

P1772 [ZJOI2006]物流运输

阅读量：4982 次

发布时间：2019-06-12

本文共 3832 字，大约阅读时间需要 12 分钟。

//Pro: 1003: [ZJOI2006]物流运输//cost[i][j]表示第i天到第j天的最短路长度//f[i]表示前i天的最小花费 //f[i]=min(f[j-1]+cost[j][i]*(i-j+1)+k) ,j<=i//输出f[n]即为答案 #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){ char c=getchar();int num=0; for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num;}const int N=105;int n,m,k,e,d;bool flag[N][N],vis[N];int cost[N][N],f[N];int head[N],num_edge;struct Edge{ int v,w,nxt;}edge[N<<3];inline void add_edge(int u,int v,int w){ edge[++num_edge].v=v; edge[num_edge].w=w; edge[num_edge].nxt=head[u]; head[u]=num_edge;}struct STA{ int id,dis; STA(int a=0,int b=0) { id=a,dis=b; } bool operator < (const STA &A) const { return dis>A.dis; }};int dis[N];priority_queue
           
             que;int dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1]=0,que.push(STA(1,0)); int now; while(!que.empty()) { now=que.top().id,que.pop(); if(vis[now]) continue; for(int i=head[now],v;i;i=edge[i].nxt) { v=edge[i].v; if(vis[v]) continue; if(dis[v]>dis[now]+edge[i].w) { dis[v]=dis[now]+edge[i].w; que.push(STA(v,dis[v])); } } } return dis[m];}int main(){ n=read(),m=read(),k=read(),e=read(); for(int i=1,a,b,c;i<=e;++i) { a=read(),b=read(),c=read(); add_edge(a,b,c); add_edge(b,a,c); } d=read(); for(int i=1,x,a,b;i<=d;++i) { x=read(),a=read(),b=read(); for(int j=a;j<=b;++j) flag[x][j]=1; } memset(cost,0x3f,sizeof(cost)); for(int i=1;i<=n;++i) { for(int j=i;j<=n;++j) { memset(vis,0,sizeof(vis)); for(int k=1;k<=m;++k) { for(int l=i;l<=j&&vis[k]==0;++l) vis[k]|=flag[k][l]; } cost[i][j]=dijkstra(); } } memset(f,0x3f,sizeof(f)); f[0]=-k; for(int i=1;i<=n;++i) { for(int j=1;j<=i;++j) { if(cost[j][i]==dis[0]) continue; if(f[i]>f[j-1]+cost[j][i]*(i-j+1)+k) f[i]=f[j-1]+cost[j][i]*(i-j+1)+k; } } printf("%d",f[n]); return 0;}

//Pro: 1003: [ZJOI2006]物流运输//cost[i][j]表示第i天到第j天的最短路长度//f[i]表示前i天的最小花费 //f[i]=min(f[j-1]+cost[j][i]*(i-j+1)+k) ,j<=i//输出f[n]即为答案 #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){ char c=getchar();int num=0; for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num;}const int N=105;int n,m,k,e,d;bool flag[N][N],vis[N];int cost[N][N],f[N];int head[N],num_edge;struct Edge{ int v,w,nxt;}edge[N<<3];inline void add_edge(int u,int v,int w){ edge[++num_edge].v=v; edge[num_edge].w=w; edge[num_edge].nxt=head[u]; head[u]=num_edge;}struct STA{ int id,dis; STA(int a=0,int b=0) { id=a,dis=b; } bool operator < (const STA &A) const { return dis>A.dis; }};int dis[N];priority_queue
           
             que;int dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1]=0,que.push(STA(1,0)); int now; while(!que.empty()) { now=que.top().id,que.pop(); if(vis[now]) continue; for(int i=head[now],v;i;i=edge[i].nxt) { v=edge[i].v; if(vis[v]) continue; if(dis[v]>dis[now]+edge[i].w) { dis[v]=dis[now]+edge[i].w; que.push(STA(v,dis[v])); } } } return dis[m];}int main(){ n=read(),m=read(),k=read(),e=read(); for(int i=1,a,b,c;i<=e;++i) { a=read(),b=read(),c=read(); add_edge(a,b,c); add_edge(b,a,c); } d=read(); for(int i=1,x,a,b;i<=d;++i) { x=read(),a=read(),b=read(); for(int j=a;j<=b;++j) flag[x][j]=1; } memset(cost,0x3f,sizeof(cost)); for(int i=1;i<=n;++i) { for(int j=i;j<=n;++j) { memset(vis,0,sizeof(vis)); for(int k=1;k<=m;++k) { for(int l=i;l<=j&&vis[k]==0;++l) vis[k]|=flag[k][l]; } cost[i][j]=dijkstra(); } } memset(f,0x3f,sizeof(f)); f[0]=-k; for(int i=1;i<=n;++i) { for(int j=1;j<=i;++j) { if(cost[j][i]==dis[0]) continue; if(f[i]>f[j-1]+cost[j][i]*(i-j+1)+k) f[i]=f[j-1]+cost[j][i]*(i-j+1)+k; } } printf("%d",f[n]); return 0;}