全部 WA 飞求调

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
int n,m,k,e,d;
struct enode {
	int nxt,to,val;
} edge[405];
int tot,head[25];
void add(int u,int v,int w) {
	edge[++tot]={head[u],v,w};
	head[u]=tot;
}
struct tim {
	int p,l,r;
} a[25];
ll dis[25],cost[105][105],dp[105]; // dp[i] 表示前 i 天的最小花费
bool avail[25],vis[25];
void dijkstra(int s) {
	for(int i=1;i<=m;i++) dis[i]=1e18,vis[i]=0;
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
	q.push({dis[s]=0,s});
	while(!q.empty()) {
		int u=q.top().se;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt) {
			int v=edge[i].to;
			if(!avail[v]) continue;
			ll w=edge[i].val;
			if(dis[v]>dis[u]+w) q.push({dis[v]=dis[u]+w,v});
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k>>e;
	for(int i=1;i<=e;i++) {
		int u,v,w;cin>>u>>v>>w;
		add(u,v,w);add(v,u,w);
	}
	cin>>d;
	for(int i=1;i<=d;i++) cin>>a[i].p>>a[i].l>>a[i].r;
	for(int l=1;l<=n;l++) {
		for(int r=l;r<=n;r++) {
			for(int i=1;i<=m;i++) avail[i]=1;
			for(int i=1;i<=d;i++)
				if(a[i].l<=r&&a[i].r>=l) avail[a[i].p]=0;
			dijkstra(1);
			cost[l][r]=dis[n];
		}
	}
	// for(int i=1;i<=n;i++) {
	// 	for(int j=1;j<=n;j++) cerr<<cost[i][j]<<" ";
	// 	cerr<<"\n";
	// }
	for(int i=1;i<=n;i++) dp[i]=cost[1][i]*i;
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
			dp[i]=min(dp[i],dp[j]+cost[j+1][i]*(i-j)+k);
	cout<<dp[n]<<"\n";
	return 0;
}