感觉自己估算的时间复杂度没有问题啊，为啥会TLE？

#include<iostream>
#include<vector>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<queue>

#define maxn 55
#define ma 2000005
#define int long long

using namespace std;

struct node{
	int x;
	int c;//用卡次数 
	int val;
};

node make_node(int num,int num2,int num3){
	node lre;
	lre.x=num;
	lre.c=num2;
	lre.val=num3;
	return lre;
}

struct edge{
	int to;
	int next;
	int val;
}e[2005];

int cnt=1;
int head[maxn];

void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].val=w;
	e[cnt].next=head[u];
	head[u]=cnt;
	cnt++;
}

int n,m,k;
int res[maxn][maxn];

priority_queue<node> q;

bool operator <(node a,node b){
	return res[a.x][a.c]<res[b.x][b.c];
}

signed main(){
	
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		head[i]=0;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			res[i][j]=ma;
		}
	}
	res[1][0]=0;
	q.push(make_node(1,0,0));
	
	while(!q.empty()){
		
		node tmp=q.top();
		q.pop();
		if((res[tmp.x][tmp.c]!=tmp.val)||(tmp.x==n)){
			continue;
		}
		
		for(int i=head[tmp.x];i;i=e[i].next){
			if(res[e[i].to][tmp.c]>res[tmp.x][tmp.c]+e[i].val){
				res[e[i].to][tmp.c]=res[tmp.x][tmp.c]+e[i].val;
				q.push(make_node(e[i].to,tmp.c,res[tmp.x][tmp.c]+e[i].val));
			}
			if(tmp.c!=k){
				if(res[e[i].to][tmp.c+1]>res[tmp.x][tmp.c]+(e[i].val/2)){
					res[e[i].to][tmp.c+1]=res[tmp.x][tmp.c]+(e[i].val/2);
					q.push(make_node(e[i].to,tmp.c+1,res[tmp.x][tmp.c]+(e[i].val/2)));
				}
			}
		}
		
	}
	
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<=k;j++){
//			cout<<res[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	
	int ans=ma;
	for(int i=0;i<=k;i++){
		ans=min(ans,res[n][i]);
	}
	cout<<ans<<endl;
	
	return 0;
}