RT, 按照时间复杂度来讲，堆优化的 $dij$ 是肯定要远快于 $spfa$ 的，但是在这一题好像？？？我的 $spfa$ 跑得比 $dij$ 快多了。请问大佬们是因为$STL$ 队列常数过大还是我写徦了

https://www.luogu.com.cn/record/38281270 (dij版本)

#include <bits/stdc++.h>
using namespace std;
#define N 110
#define ll long long
const ll inf = (ll)1e12 + 10; 

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ; 
}

struct node{
	int v, next;
	int w;
	
	node(int v = 0, int w = 0, int next = 0){
		this -> v = v;
		this -> w = w;
		this -> next = next;
		return ; 
	}
} t[1000010];
int f[N]; 

int bian = 0;
inline void addedge(int u, int v, int w){
	t[++bian] = node(v, w, f[u]), f[u] = bian;
	t[++bian] = node(u, w, f[v]), f[v] = bian;
	return ;
}

ll dp[N]; 
ll d[N];  
int n, m, k, e; 

vector <int> G[N]; 
ll cost[N][N];
bool vis[N], ban[N];  

struct point{
	int u, dis;
	
	bool operator < (const point& a) const{
		return dis > a.dis; 
	}
};

void dij(int s){
	priority_queue <point> q; 
	for(int i = 1; i <= n; i++) vis[i] = 0, d[i] = inf;
	d[s] = 0;
	q.push((point){s, 0});
	
	while(!q.empty()){
		int now = q.top().u; q.pop();
		if(!vis[now]){
			vis[now] = 1;
			for(int i = f[now]; i; i = t[i].next){
				int v = t[i].v;
				if(ban[v]) continue;
				if(d[v] > d[now] + t[i].w){
					d[v] = d[now] + t[i].w;
					if(!vis[v]) q.push((point){v, d[v]}); 
				}
			}
		}
	}
	return ; 
}

int main(){ 
	read(m), read(n), read(k), read(e);
	for(int i = 1; i <= e; i++){
		int x, y, w; 
		read(x), read(y), read(w);
		addedge(x, y, w); 
	}
	int sum;
	read(sum);
	for(int i = 1; i <= sum; i++){
		int num, a, b;
		read(num), read(a), read(b);
		for(int j = a; j <= b; j++)
			G[j].push_back(num); 		
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= m; j++){
			memset(ban, 0, sizeof(ban));
			for(int k = i; k <= j; k++)
				for(int l = 0; l < G[k].size(); l++)
					ban[G[k][l]] = 1; 
			dij(1);
			cost[i][j] = d[n]; 		
		}
	}
	for(int i = 1; i <= m; i++) dp[i] = inf; 
	for(int i = 1; i <= m; i++){
		dp[i] = cost[1][i] * i; 
		for(int j = i-1; j >= 0; j--){ 
			dp[i] = min(dp[j] + cost[j+1][i] * (i-j) + k, dp[i]);
		}
	}
	cout << dp[m] << endl;
	return 0; 
}

https://www.luogu.com.cn/record/38281084 (spfa版本)

#include <bits/stdc++.h>
using namespace std;
#define N 110
#define ll long long
const ll inf = (ll)1e12 + 10; 

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ; 
}

struct node{
	int v, next;
	int w;
	
	node(int v = 0, int w = 0, int next = 0){
		this -> v = v;
		this -> w = w;
		this -> next = next;
		return ; 
	}
} t[1000010];
int f[N]; 

int bian = 0;
inline void addedge(int u, int v, int w){
	t[++bian] = node(v, w, f[u]), f[u] = bian;
	t[++bian] = node(u, w, f[v]), f[v] = bian;
	return ;
}

ll dp[N]; 
ll d[N];  
int n, m, k, e; 

vector <int> G[N]; 
ll cost[N][N];
bool vis[N], ban[N];  


void spfa(int s){
	queue <int> q; 
	for(int i = 1; i <= n; i++) d[i] = inf, vis[i] = 0;
	d[s] = 0;
	vis[s] = 1;
	q.push(s);
	
	while(!q.empty()){
		int now = q.front(); q.pop();
		vis[now] = 0;
		for(int i = f[now]; i; i = t[i].next){
			int v = t[i].v;
			if(ban[v]) continue; 
			if(d[v] > d[now] + t[i].w) {
				d[v] = d[now] + t[i].w;
				if(!vis[v]) 
					q.push(v), vis[v] = 1; 
			}
		}
	}
	return ; 
}

int main(){ 
	read(m), read(n), read(k), read(e);
	for(int i = 1; i <= e; i++){
		int x, y, w; 
		read(x), read(y), read(w);
		addedge(x, y, w); 
	}
	int sum;
	read(sum);
	for(int i = 1; i <= sum; i++){
		int num, a, b;
		read(num), read(a), read(b);
		for(int j = a; j <= b; j++)
			G[j].push_back(num); 		
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= m; j++){
			memset(ban, 0, sizeof(ban));
			for(int k = i; k <= j; k++)
				for(int l = 0; l < G[k].size(); l++)
					ban[G[k][l]] = 1; 
			spfa(1);
			cost[i][j] = d[n]; 		
		}
	}
	for(int i = 1; i <= m; i++) dp[i] = inf; 
	for(int i = 1; i <= m; i++){
		dp[i] = cost[1][i] * i; 
		for(int j = i-1; j >= 0; j--){ 
			dp[i] = min(dp[j] + cost[j+1][i] * (i-j) + k, dp[i]);
		}
	}
	cout << dp[m] << endl;
	return 0; 
}