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

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n,u,k,m,d;
long long f[N];
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++){
            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];
        }
    }
    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);
        //dp方程 加ll！！！ 
    }
    printf("%lld\n",f[u]);
    
    return 0;
    
}