题目链接

• D - path
  • 图论中使用优先队列的有趣题目，求一张图中第k短的路径。
  • 注意区别于“第k短路”，因为“第k短路”问题是两个定点之间的第k短，而本题没有定点。
  • 注意到第k短的路径最多只有k条边。
  • 做法：优先队列维护路径的终点、长度、终点的上一个点、终点的上一个点到终点这条边在邻接表中的编号，优先级按长度升序。预处理要将邻接表中存的边都按照权值升序排序。首先将所有简单的边作为路径放进优先队列，此时堆顶元素即为第1短路。然后在当前为第i短路的情况下，更新以下两条路径：1、堆中最短的路径后面加上终点所连最短的一条边；2、堆中最短路径的最后一条边换成次大的边。更新完这两条路径之后，堆顶元素即变为第i+1短路。记录答案即可得解。
  • 注意要离线对讯问处理。

代码：

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct Edge
{
	int v,w;
	bool operator<(const Edge&b)const
	{
		return w<b.w;
	}
};
struct Road
{
	int s,last_t,t,ind;
	long long w;
	bool operator<(const Road&b)const
	{
		return w>b.w;
	}
};
vector<Edge>edge[(int)5e4+10];
int query[(int)5e4+10];
long long ans[(int)5e4+10];
priority_queue<Road>pq;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		while(!pq.empty())
		{
			pq.pop();
		}
		int n,m,q;
		scanf("%d%d%d",&n,&m,&q);
		for(int i=1;i<=n;++i)
		{
			edge[i].clear();
		}
		Edge tmp_edge;
		for(int i=0;i<m;++i)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			tmp_edge.v=v;
			tmp_edge.w=w;
			edge[u].push_back(tmp_edge);
		}
		for(int i=1;i<=n;++i)
		{
			sort(edge[i].begin(),edge[i].end());
		}
		int max_query=0;
		for(int i=0;i<q;++i)
		{
			scanf("%d",&query[i]);
			max_query=max(query[i],max_query);
		}
		Road road_tmp;
		for(int i=1;i<=n;++i)
		{
			if(edge[i].size())
			{
				road_tmp.s=road_tmp.last_t=i;
				road_tmp.t=edge[i][0].v;
				road_tmp.ind=0;
				road_tmp.w=edge[i][0].w;
				pq.push(road_tmp);
			}
		}
		int current=1;
		int s,t,last_t,ind;
		long long w;
		Road next;
		while(current<=max_query)
		{
			ans[current]=pq.top().w;
			s=pq.top().s;
			t=pq.top().t;
			last_t=pq.top().last_t;
			ind=pq.top().ind;
			w=pq.top().w;
			if(ind<edge[last_t].size()-1)
			{
				next.s=s;
				next.last_t=last_t;
				next.ind=ind+1;
				next.t=edge[last_t][next.ind].v;
				next.w=w-edge[last_t][ind].w+edge[last_t][next.ind].w;
				pq.push(next);
			}
			if(edge[t].size())
			{
				next.s=s;
				next.last_t=t;
				next.ind=0;
				next.t=edge[t][next.ind].v;
				next.w=w+edge[t][next.ind].w;
				pq.push(next);
			}
			pq.pop();
			++current;
		}
		for(int i=0;i<q;++i)
		{
			printf("%lld\n",ans[query[i]]);
		}
	}
	return 0;
}