Tokitsukaze and Slash Draw - 最短路

本文主要是介绍Tokitsukaze and Slash Draw - 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

每一种操作可以认为当前位置移动 $a$ 个位置到达之后的位置，花费为 $b$，也就是可以理解为从 $i$ 到 $(i+a)modn$存在一条边，边权为 $b$，那么就可以进行最短路来计算最小权值。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;void solve() {int n, m, k;cin >> n >> m >> k;vector<vector<pair<int, int>>> adj(n);while(m --) {int a, b;cin >> a >> b;for(int i = 0; i < n; i ++) adj[i].push_back({(i + a) % n, b});}if(k == n) {cout << "0\n";return ;}vector<ll> dis(n, 1e17);vector<int> st(n, 0);auto dijkstra = [&](int k) {priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> heap;heap.push({0, k});dis[k] = 0;while(heap.size()) {auto t = heap.top();heap.pop();if(st[t.second]) continue;st[t.second] = 1;for(auto j: adj[t.second]) {if(dis[j.first] > dis[t.second] + j.second) {dis[j.first] = dis[t.second] + j.second;heap.push({dis[j.first], j.first});}}}};dijkstra(k);if(dis[0] == 1e17) cout << "-1\n";else cout << dis[0] << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}

这篇关于Tokitsukaze and Slash Draw - 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---