求调!!!
查看原帖
求调!!!
673962
lzs18637466689楼主2024/11/29 20:48
请求大佬帮助!!

只过了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;
}
2024/11/29 20:48
加载中...