记录编号	584242	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2006] 物流运输	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2023-11-03 21:40:22	内存使用	1.74 MiB

#include <bits/stdc++.h>
using namespace std;
//最短路 + dp 
const int N = 110;
int n,u,k,m,d;
long long f[N];//dp数组前i天最小费用 
int s[N][N],v[N];
struct node{
    int x,l,r;
}a[N];//限制 
struct made{
    int ver,nx,ed;
}e[N<<2];
int hd[N],tot;
void add(int x,int y,int z){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],e[tot].ed = z,hd[x] = tot;
}//图 
int di[N],v1[N];
void spfa(){//最短路 想跑啥跑啥 
    queue<int>q;
    memset(di,0x3f,sizeof(di));
    memset(v1,0,sizeof(v1));
    q.push(1);v1[1] = 1;di[1] = 0;
    while(!q.empty()){
        int x = q.front();q.pop();
        v1[x] = 0;
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver,z = e[i].ed;
            if(v[y])continue;//不能走的节点 
            if(di[x] + z < di[y]){
                di[y] = di[x] + z;
                if(!v1[y])v1[y] = 1,q.push(y);
            }
        }
    }
}
int main(){
    freopen("bzoj_1003.in","r",stdin);
    freopen("bzoj_1003.out","w",stdout);
    scanf("%d%d%d%d",&u,&n,&k,&m);
    for(int i = 1;i <= m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    scanf("%d",&d);
    for(int i = 1;i <= d;i++)scanf("%d%d%d",&a[i].x,&a[i].l,&a[i].r);
    for(int i = 1;i <= u;i++){
        for(int j = i;j <= u;j++){//u！！！！ 
            memset(v,0,sizeof(v));
            for(int k = 1;k <= d;k++)
                if(i <= a[k].r && j >= a[k].l)v[a[k].x] = 1;//限制 
            spfa();// 
            s[i][j] = di[n];
        }//s[i][j]表示第i天到第j天的最短路 
    }
    memset(f,0x7f,sizeof(f));
    for(int i = 1;i <= u;i++){
        f[i] = 1ll * s[1][i] * i;//不换路 
        for(int j = 1;j < i;j++)f[i] = min(f[i],f[j] + 1ll * s[j+1][i] * (i-j) + k);//从j天换路 
        //dp方程 加ll！！！ 
    }
    printf("%lld\n",f[u]);
    
    return 0;
    
}