题解 | 最短？路径（分层最短路）

最短？路径：原题链接

题意：

     有n个点m条边和不休息次数k，希望你从点1出发到达点n。当你抵达一个点时，你有两种选择：1.休息，消耗ai的时间，2.不休息，消耗1的时间。

注：当不休息次数达到k时，此时必须在该点休息。

做题思路：

     从点出发到达某点，很显然是最短路问题，但考虑到存在休息这一条件，因此使用分层最短路进行求解。（是不是做过...链接【|||--】)。

     分层最短路，将最短路原先的二维地图，转变为三维，其中多出的z轴通常会是最短路多出的变量条件，本题设置k，作为分层的层数。

     首先对每个点消耗的时间和能够建立的桥梁（边）进行读取。

		cin >>n>>m>>k;
		vector<int> a(n + 1);
		//在每个点休息时的代价
		for (int i = 1; i <= n; i++)cin >> a[i];
		vector<vector<int>> edges(n + 1);
		//建立双向边
		for (int i = 1; i <= m; i++)
		{
			cin >>from>>to;
			edges[from].push_back(to);
			edges[to].push_back(from);
		}

     因为需要多次输入，所以这里直接将数组开在了内部，因此，需要对数组进行初始化处理。

//初始化节点
void init(){
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			//为了查找出耗时最少的路径，先将所有节点初始化为最大值
			d[i][j] =1e18;
			vis[i][j] = 0;
		}
	}
}

     处理完后，就是常规的djkstra代码。

		//优先队列：保证每次花费最少时间到达下一个点
		priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
		//初始k不为0时，初始地图有两张
		if (k!=0)
		{
			//设置level=1的地图的第1个点，消耗的时间为1
			d[1][1]=1;
			q.push({1,1,1});
		}
		//不论k是否为0，level为0的地图都将存入第1个原本的消耗时间
		d[1][0]=a[1];
		q.push({a[1], 1, 0});
		while (q.size())
		{
			auto [w,i,level] = q.top();
			q.pop();
			//当该层的点被走过时，跳过本次循环
			if (vis[i][level])continue;
			vis[i][level] = 1;
			//遍历该点拥有的桥梁，优先队列保证最先遍历的一定会是消耗最少时间的桥梁
			for (auto to: edges[i])
			{
				//分别举例休息和不休息时两种情况的耗时情况
				//休息
				if (d[to][0] > a[to] + w)
				{
					//确保行进到当前位面的节点最小
					d[to][0] = a[to] + w;
					q.push({d[to][0],to, 0});
				}
				//不休息
				// level+1<=k:代表还能够不休息时
				if (level+1<=k && d[to][level+1]>w+1)
				{
					// 同理替换
					d[to][level+1]=w+1;
					q.push({d[to][level+1],to,level+1});
				}
			}
		}

     因此最后只要遍历每层的n点，就能得出最小的消耗时间了，这里直接上ac代码：

#include<bits/stdc++.h>
// 使int变更为long long
#define int long long
using namespace std;

const int N = 2e5+10;
int t,n,m,k,from,to;
int d[N][11];
int vis[N][11];

//初始化节点
void init(){
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			//为了查找出耗时最少的路径，先将所有节点初始化为最大值
			d[i][j] =1e18;
			vis[i][j] = 0;
		}
	}
}
// 更改Int后，请使用signed形式
signed main() {
	cin >> t;
	while (t--) {
		cin >>n>>m>>k;
		vector<int> a(n + 1);
		//在每个点休息时的代价
		for (int i = 1; i <= n; i++)cin >> a[i];
		vector<vector<int>> edges(n + 1);
		//建立双向边
		for (int i = 1; i <= m; i++)
		{
			cin >>from>>to;
			edges[from].push_back(to);
			edges[to].push_back(from);
		}
		init();
		//dijkstra部分
		//优先队列：保证每次花费最少时间到达下一个点
		priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
		//初始k不为0时，初始地图有两张
		if (k!=0)
		{
			//设置level=1的地图的第1个点，消耗的时间为1
			d[1][1]=1;
			q.push({1,1,1});
		}
		//不论k是否为0，level为0的地图都将存入第1个原本的消耗时间
		d[1][0]=a[1];
		q.push({a[1], 1, 0});
		while (q.size())
		{
			auto [w,i,level] = q.top();
			q.pop();
			//当该层的点被走过时，跳过本次循环
			if (vis[i][level])continue;
			vis[i][level] = 1;
			//遍历该点拥有的桥梁，优先队列保证最先遍历的一定会是消耗最少时间的桥梁
			for (auto to: edges[i])
			{
				//分别举例休息和不休息时两种情况的耗时情况
				//休息
				if (d[to][0] > a[to] + w)
				{
					//确保行进到当前位面的节点最小
					d[to][0] = a[to] + w;
					q.push({d[to][0],to, 0});
				}
				//不休息
				// level+1<=k:代表还能够不休息时
				if (level+1<=k && d[to][level+1]>w+1)
				{
					// 同理替换
					d[to][level+1]=w+1;
					q.push({d[to][level+1],to,level+1});
				}
			}
		}
		// 最后查找
		int ans = 1e18;
		// 便利每层位面的n节点，找出最小的消耗量
		for (int level = 0; level <= k; level++)ans = min(ans, d[n][level]);
		cout <<ans<<"\n";
	}
	return 0;
}