题意:
中文所示
思路:
如果没有限制条件，那么就是最短路，每个点只有一种状态，有了这个限制条件，每个点的状态变为\(2k\)种, 所以相当于求每个\(2k\)种状态的最优情况，要得到这\(2k\)种状态，相当于在原先的最短路中，不把让每个点尽可能的跑，直到不符合条件，所以就相当于多一维状态，最短路可以对每一种状态都求得最优值，所以最后的答案就是在所有的状态了里面取最优解
总结：
最短路能够得到从a->b点的最有状态，最普通的最短路，就是每一个点一种状态，如果每个点有多个状态，那就让他不断的跑，知道遇到不能跑为止，这些状态在最短路跑完后，每一种状态也是最优解，因为最短路的性质就是对于能够有多条路径能到达这个状态的取最优的那种状态
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 1e4 + 10;
const int inf = 0x3f3f3f3f;
int T, n, m, k, a, b;
int val[MAXN], dis[MAXN][30];
struct Node
{
int ver, dis, state;
};
vector<Node> edge[MAXN];
class comp
{
public:
bool operator()(Node x, Node y)
{
return x.dis > y.dis;
}
};
void init()
{
for (int i = 1; i <= n; ++i)
edge[i].clear();
}
void Dijkstra(int a)
{
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= 2 * k; ++j)
dis[i][j] = inf;
dis[a][k + val[a]] = 0;
priority_queue<Node, vector<Node>, comp> heap;
heap.push({a, dis[a][k + val[a]], k + val[a]});
while (!heap.empty())
{
Node now = heap.top();
heap.pop();
for (int i = 0; i < edge[now.ver].size(); ++i)
{
int y = edge[now.ver][i].ver;
int statey = now.state + val[y];
//cout << "y: " << y << endl;
if (statey < 0 || statey > 2 * k)
continue;
if (dis[y][statey] > dis[now.ver][now.state] + edge[now.ver][i].dis)
{
dis[y][statey] = dis[now.ver][now.state] + edge[now.ver][i].dis;
heap.push({y, dis[y][statey], statey});
}
}
}
}
int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> n >> m >> k;
init();
for (int i = 1, x; i <= n; ++i)
cin >> x, (x == 1 ? val[i] = 1 : val[i] = -1);
for (int i = 1, x, y, t; i <= m; ++i)
cin >> x >> y >> t, edge[x].push_back({y, t}), edge[y].push_back({x, t});
cin >> a >> b;
Dijkstra(a);
int ans = inf;
for (int i = 0; i <= 2 * k; ++i)
ans = min(ans, dis[b][i]);
cout << (ans == inf ? -1 : ans) << endl;
}
return 0;
}