请求大佬帮助!!
只过了2个测试点
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5e5 + 10, M = 5e6 + 10;
typedef pair<int,int> PII;
int n, m, k;
int s, t;
int dist[N];
bool st[N];
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
priority_queue<PII,vector<PII>,greater<PII> >heap;//定义小根堆;
dist[s] = 0;
heap.push({0, 1});
while(!heap.empty())
{
PII t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = min(distance + w[i], dist[j]);
heap.push({dist[j], j});
}
}
}
return dist[t + n*k];
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> k;
cin >> s >> t;
while( m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a ,c);//无向图
/*
分层图的解决思路:
将图进行分层,建k + 1层图,每层内正常建边,
层与层之间用权值为0的边相连,然后应用最短路算法求解即可。
*/
for(int i = 1; i <= k; i ++){
add(a + (i - 1)*n,b + i*n,0);//建0边
add(b + (i - 1)*n,a + i*n,0);
//-----------------------------------分割线------------------------------------------------------------
add(a + i*n,b + i*n,c);// 每层正常建边
add(b + i*n,a + i*n,c);
}
}
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
/*
当然还会出现一种特殊情况:最短路径上的总边数小于k,
也就是说可能最短路径在中间某层的汇点就已经达到了0,
再向下走反而会使总路径增大。为了避免这种情况,
我们可以在每两个相邻层的汇点之间连接一条权值为0的边。
*/
for(int i = 1; i <= k; i ++)
add(t + (i-1) * n, t + i*n, 0);
//防止毒瘤数据,k 次机会还没用完就到终点了。。
cout << dijkstra() ;
return 0;
}