没有用dp的一种解法

本题的测试数据真的有点水，以至于我在忽略了一些重要细节的情况下都AC了
  • 如果你也通过了这题但感觉有哪里不对劲，可以来看看这个题解
  • 我不能保证我修改过的题解一定能严格通过题意，建议还是学习一下大佬用dp的题解

说说做法

  • 这题除了多了一个k之外就是最短路的板题
  • 处理k：定义一个st【N】表示到i点已经积累的***点数量，比k大的话就不能再向下走了，st数组的处理方式与dist路径相似

说说我一开始都犯了什么错

  1. 因为w比较大，所以我一开始给dist开了long long，但是最后判断能不能过的时候用了int的inf，以至于我根本不可能输出*-1*这个答案
  2. 一开始我用到的判断方法是*if (st[pos] > k)continue;*问题在于，我已经得到了到pos点的最短路，那我就无法再更新pos点链接的路径（pos点可能链接通向终点的唯一路径）看不懂没关系，看测试用例吧

/* 补充测试用例

5 5 2

1 1 1 0 1

1 2 5

1 4 10

2 3 5

4 3 10

3 5 0

1->4->3->5是一条有效路径，但不是无视k下的最短路

1->2->3->5是最短路，但不满足题目对k的限制 */

原做法是通不过这个用例的，问题是，原做法在这俩个错误下AC了（显然测试用例还不够严格）

以下是修改过的题解

判断条件改成了 if (st[pos] + warn[to] > k) continue;

这样当pos的下一个点无法再向下走时，我们不去计算那个点的最短路，不让它入队，就不会和最短路判断产生矛盾

记得要将warn[n] = 0,因为我们不需要再通过n前往任何地方，warn[n] = 1反而会影响到答案的判断

/*2024.2.24 邻接表*/
//longlong 警告
//如果在一条路径上***点超过上限，就不再走
//WA: 取数时忘记弹出pq了
//WA：推测是过***点的数的计算有问题
//我总觉得这样写会有问题
//WA：不用longlong（最坏800*1e6），而且这样最后不能用0x3f3f3f3f判断
//这个方法确实有问题(已修改)
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int maxn = 810;
const int maxm = 4010*2;
int n, m, k;
int dist[maxn];
int st[maxn];//到i点已经积累的***点
/* 补充测试用例
5 5 2
1 1 1 0 1
1 2 5
1 4 10
2 3 5
4 3 10
3 5 0
1->4->3->5是一条有效路径，但不是无视k下的最短路
1->2->3->5是最短路，但不满足题目对k的限制
*/
struct Node {
	int to;
	int w;
};
bool warn[maxn];//i点是否为***点
vector<Node> node[maxn];
void dijk() {
	priority_queue < PII, vector<PII>, greater<PII>> pq;
	pq.push({ 0, 1 });
	dist[1] = 0;
	st[1] = warn[1] ? 1 : 0;
	warn[n] = 0;//我们不需要再通过n前往任何地方，warn[n] = 1反而会影响到答案的判断
	while (pq.size()) {
		auto t = pq.top();
		pq.pop();
		int pos = t.second;
		for (int i = 0; i < node[pos].size(); i++) {
			int to = node[pos][i].to;
			int w = node[pos][i].w;
			if (dist[to] <= dist[pos] + w) continue;
			if (st[pos] + warn[to] > k) continue;//通过这个点还有没有向下走的可能
			//if (st[pos] > k) continue; //一开始用到判断方法
			dist[to] = dist[pos] + w;
			st[to] = st[pos] + warn[to];
			pq.push({ dist[to],to });
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> warn[i];
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		node[u].push_back({ v,w });
		node[v].push_back({ u,w });
	}
	dijk();
	if (dist[n] == 0x3f3f3f3f) cout << -1 << "\n";
	else cout << dist[n] << "\n";
	return 0;
}