自认为代码思路清晰

目前对拍出来的情况是：如果没有免费搭乘算法可以求出最短路，但如果有，貌似还会使原来不用免费搭乘的最短路变得比答案更大（他在没有免费搭乘的时候是还是正确的啊）

比如这个数据

13 22 3
6 3
5 12 5
0 10 4
3 10 18
9 3 6
10 12 16
9 1 2
10 11 19
11 7 2
8 6 9
6 9 13
2 4 20
4 6 18
5 1 13
4 11 9
5 10 10
10 3 2
1 11 19
9 10 18
8 5 1
12 1 20
10 5 2
12 0 16

6号出发，如果我们删去代码中的if(cnt < k)部分，求出的6 -> 1的最短路是正确的，是15。但如果加上，就会发现同样是不免费搭乘，他求出的结果反而成了23……

求调试，谢谢大佬，关注您

#include <iostream>
#include <string.h>
#include <set>
using namespace std;

inline int read();

int n,m,k;
int s,t;

struct Edge{
	int v,w,nxt;
}e[100005];
int p[10005],eid;

inline void init(){
	memset(p,-1,sizeof(p));
	eid = 0;
}

inline void insert(int u,int v,int w){
	e[eid].v = v;
	e[eid].w = w;
	e[eid].nxt = p[u];
	p[u] = eid++;
}

int dis[10005][15];

struct NODE{
	int u,cnt,dis;
	NODE(int uu = 0,int cntt = 0,int diss = 0){
		u = uu,cnt = cntt,dis = diss;
	}
};

bool operator < (NODE x,NODE y){
	return x.dis < y.dis;
}

set <NODE> min_heap;

int main(){
	//freopen("in.in","r",stdin);
	init();
	n = read();
	m = read();
	k = read();
	s = read();
	t = read();
	for(int i = 1;i <= m;++i){
		int u,v,w;
		u = read();
		v = read();
		w = read();
		insert(u,v,w);
		insert(v,u,w);
	}
	memset(dis,0x3f3f3f3f,sizeof(dis));
	for(int i = 0;i <= k;++i) dis[s][i] = 0;
	min_heap.insert(NODE(s,0,0));
	while(!min_heap.empty()){
		NODE tmp = *min_heap.begin();
		min_heap.erase(min_heap.begin());
		int u = tmp.u;
		int cnt = tmp.cnt;
		for(int i = p[u];i != -1;i = e[i].nxt){
			int v = e[i].v;
			if(dis[v][cnt] > dis[u][cnt] + e[i].w){
				min_heap.erase(NODE(v,cnt,dis[v][cnt]));
				dis[v][cnt] = dis[u][cnt] + e[i].w;
				min_heap.insert(NODE(v,cnt,dis[v][cnt]));
			}
			if(cnt < k){
				if(dis[v][cnt + 1] > dis[u][cnt]){
					min_heap.erase(NODE(v,cnt + 1,dis[v][cnt + 1]));
					dis[v][cnt + 1] = dis[u][cnt];
					min_heap.insert(NODE(v,cnt + 1,dis[v][cnt + 1]));
				}
			}
		}
	}
	int minn = 1000000000;
	for(int i = 0;i <= k;++i){
		minn = min(minn,dis[t][i]);
	}
	for(int i = 1;i <= n;++i){
		for(int j = 0;j <= k;++j){
			printf("%d ",dis[i][j]);
		}
		printf("\n");
	}
	printf("%d",minn);
	return 0;
}

inline int read(){
	register int w = 0,flag = 1;
	register char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') flag = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		w = (w << 3) + (w << 1) + (c ^ 48);
		c = getchar();
	}
	return w * flag;
}