Dijkstra堆优化+dp WA30pts求调（#1，#2，#5对）

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define MAXN 210
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

struct edge{
	ll v,w;
};

struct node{
	int inx,dist;
	int path;
	bool operator<(const node& o) const{
		return o.dist<dist;
	}
};

ll n,m,ks,e,d;
ll u[MAXN],v[MAXN],w[MAXN];
ll f[MAXN];
bool flag[30][110];
bool mark[MAXN];
vector<edge> G[MAXN];
priority_queue<node> qp;
node nd[MAXN];
ll at_now[MAXN],cnt;

ll fminn(ll a,ll b){ return a<b?a:b; }

void init(){
	for(int i=1;i<=m;i++){
		nd[i].inx=i;
		nd[i].dist=INF;
		nd[i].path=-1;
	}
	nd[1].dist=0;
	while(!qp.empty()) qp.pop();
	memset(at_now,0,sizeof(at_now));
	memset(mark,false,sizeof(mark));
	cnt=0;
	return ;
}

ll Dijkstra(int now){
	init();
	for(int i=1;i<=m;i++) G[i].clear(),G[i].resize(0);
	for(int i=1;i<=e;i++){
		if(flag[u[i]][now]||flag[v[i]][now]) continue;
		G[u[i]].push_back((edge){v[i],w[i]});
		G[v[i]].push_back((edge){u[i],w[i]});
	}
	qp.push((node){1,0,-1});
	while(!qp.empty()){
		node tk=qp.top();
		qp.pop();
		int k=tk.inx;
		if(mark[k]) continue;
		mark[k]=true;
		for(int i=0;i<(int)G[k].size();i++){
			int ij=G[k][i].v;
			if(G[k][i].w+nd[k].dist<=nd[ij].dist){
				nd[ij].dist=G[k][i].w+nd[k].dist;
				nd[ij].path=k;
				if(!mark[ij]){
					qp.push((node){ij,nd[ij].dist,k});
				}
			}
		}
	}
	return nd[(int)m].dist;
}

void print_path(int ttt){
	//cout<<ttt<<" "<<nd[ttt].path<<endl;
	if(nd[ttt].path!=-1){
		print_path(nd[ttt].path);
	}
	at_now[++cnt]=ttt;
	return ;
}

bool check(int past){
	for(int i=1;i<=cnt;i++){
		if(flag[at_now[i]][past]){
			return true;
		}
	}
	return false;
}

int main(){
	cin>>n>>m>>ks>>e;
	for(int i=1;i<=e;i++){
		cin>>u[i]>>v[i]>>w[i];
		//G[u].push_back((node){v,w});
	}
	cin>>d;
	for(int i=1;i<=d;i++){
		ll p,a,b;
		cin>>p>>a>>b;
		for(int j=a;j<=fminn(b,n);j++){
			flag[p][j]=true;
		}
	}
	f[0]=-ks;
	for(int i=1;i<=n;i++){
		f[i]=INF;
		ll asd=Dijkstra(i);
		int j=i;
		print_path(m);
		while(true){
			if(j==0){
				break;
			}
			if(check(j)){
				break;
			}
			j--;
		}
		f[i]=fminn(f[i],f[j]+(i-j)*asd+ks);
	}
	cout<<f[n];
	return 0;
}