#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
int n,m,k,e,D;
int ver[1010],ne[1010],edge[1010],he[1010],tot;
void add(int u,int v,int w){
	ver[++tot]=v;
	ne[tot]=he[u];
	he[u]=tot;
	edge[tot]=w;	
} 
struct node{
	int w,to;
	bool operator <(const node &a)const{
		return w<a.w;
	}
};
bool vis[1010],flag[1010]; 
int d[1010],co[1010][1010],f[1010];
void dij(){
	priority_queue<node>q;
	q.push({0,1}); 
	for(int i=1;i<=m;++i) d[i]=1e9; 
	d[1]=0;
	while(!q.empty()){
		int u=q.top().to; q.pop();
		if(vis[u]) continue; vis[u]=1;
		for(int i=he[u];i;i=ne[i]){
//			cout<<99999;
			int v=ver[i],w=edge[i];
			if(flag[v]==1) continue;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w; 
				q.push({-d[v],v});
			}
		}
	}
}
void spfa(){
	for(int i=1;i<=m;++i) d[i]=1e9;
	queue<int>q;
	d[1]=0;
	q.push(1);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=he[x];i;i=ne[i]){
			int v=ver[i],w=edge[i];
			if(flag[v]) continue;
			if(d[v]>d[x]+w){
				d[v]=d[x]+w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
//vector<node>v[1010];
int no[1010][1010];//city i is not available on day j
signed main(){
	cin>>n>>m>>k>>e;
	for(int i=1;i<=e;++i){
		int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w); add(v,u,w);
	}
	cin>>D;
	for(int i=1;i<=D;++i){
		int p,a,b; scanf("%lld%lld%lld",&p,&a,&b);
//		v[p].push_back({a,b});
		for(int j=a;j<=b;++j) no[p][j]=1;
	}
//	for(int i=1;i<=5;++i,cout<<endl)
//		for(int j=1;j<=5;++j) cout<<no[i][j];
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			//not available
			memset(flag,0,sizeof flag);
			for(int k=1;k<=m;++k)
				for(int l=i;l<=j;++l) if(no[k][l]) flag[k]=1;
			spfa();
			co[i][j]=d[m]; 
// 			cout<<d[m]<<endl;
		}
	memset(f,0x7f,sizeof f);
	for(int i=1;i<=n;++i){
		f[i]=co[1][i]*i;//initialize
		for(int j=i-1;j>=0;--j)
			f[i]=min(f[i],f[j]+k+co[j+1][i]*(i-j));		
	}
	cout<<f[n]<<endl;
	return 0;
}

代码里面如果不调用 spfa 改成 dij 的话 d[m] 就会一直是 inf，同时如果 spfa 中 for(int i=1;i<=m;++i) d[i]=1e9; 改成 memset(d,0x3f,sizeof d); 也会有问题

为什么阿