众所周知，dij 一遍跑次短路是不能加标记的。
但是这道题必须要打标记不然过不了/dk
这是代码

#include <iostream>
#include <vector>
#include <queue> 
#include <cstring> 
#define MAXN 100000
#define SX  cnt[u][fr.tp]
#define QWQ cout << "QWQ" << endl;
using namespace std;
struct node {
	int to, val, tp;
	node(int T, int V, int TP) {
		to = T, val = V, tp = TP;
	}
	bool operator < (const node &other) const {
		return val > other.val;
	}
};
//tp = 0 最短路 tp = 1 次短路  
int dis[MAXN + 10][2], cnt[MAXN + 10][2];
bool vis[MAXN + 10][2];
vector <node> gra[MAXN + 10];
int s, t;
void dijkstra() {
	for(int p = 1; p <= MAXN; p++) dis[p][0] = dis[p][1] = 0x3f3f3f3f;
	for(int p = 1; p <= MAXN; p++) vis[p][0] = vis[p][1] = 0, cnt[p][0] = cnt[p][1] = 0;
	dis[s][0] = 0;
	cnt[s][0] = 1;
	priority_queue <node> que;
	que.push(node(s, 0, 0));
	while(!que.empty()) {
		node fr = que.top(); que.pop();
		int u = fr.to, dist = fr.val; 
		if(vis[u][fr.tp]) continue;
		vis[u][fr.tp] = 1;
		for(int p = 0; p < gra[u].size(); p++) {
			int v = gra[u][p].to;
			if(dis[v][0] == dist + gra[u][p].val) cnt[v][0] += SX; 
			else if(dis[v][0] > dist + gra[u][p].val) {
				dis[v][1] = dis[v][0], cnt[v][1] = cnt[v][0];
				que.push(node(v, dis[v][1], 1));
				dis[v][0] = dist + gra[u][p].val, cnt[v][0] = SX;
				que.push(node(v, dis[v][0], 0));
			}
			else if(dis[v][1] > dist + gra[u][p].val && dist + gra[u][p].val > dis[v][0]) {
				dis[v][1] = dist + gra[u][p].val, cnt[v][1] = SX;
				que.push(node(v, dis[v][1], 1));
			}
			else if(dis[v][1] == dist + gra[u][p].val) cnt[v][1] += SX;
		}
	}
}
void solve() {
	dijkstra();
	if(dis[t][1] - dis[t][0] != 1) {
		cout << cnt[t][0] << endl;
		return ;
	}
	else cout << cnt[t][0] + cnt[t][1] << endl;
}
int main() {
	int T; cin >> T;
	while(T--) {
		int n, m;
		cin >> n >> m;
		for(int p = 1, x, y, z; p <= m; p++) {
			cin >> x >> y >> z;
			gra[x].push_back(node(y, z, 0));
		}
		cin >> s >> t;
		solve();
		for(int p = 1; p <= MAXN; p++) gra[p].clear();
	}
}

但是次短路理应不应该行啊，因为次短路可能多次入队（晕乎乎
求助/wq