Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define pb push_back
- #include <iostream>
- #include <climits>
- #include <algorithm>
- #include <iomanip>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <string>
- #include <stack>
- #include <set>
- #include <cstdio>
- #include <cctype>
- #include <queue>
- #include <bitset>
- #include <functional>
- #include <cassert>
- #include <unordered_map>
- using namespace std;
- #define int long long
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- typedef long double ld;
- typedef double db;
- const ll N = 1e4 + 10;
- const ll INF = LLONG_MAX;
- /*
- struct node {
- node *l, *r;
- int x, y;
- int sum;
- int val;
- node(int s) {
- l = nullptr;
- r = nullptr;
- y = rand();
- sum = s * s;
- val = s;
- x = 1;
- }
- };
- int getx(node* v) {
- if (v == nullptr) return 0;
- return v->x;
- }
- int getsum(node* v) {
- if (v == nullptr) return 0;
- return v->sum;
- }
- void upd(node* v) {
- if (v == nullptr) return;
- v->sum = getsum(v->l) + getsum(v->r);
- }
- pair<node*, node*> split(node*& root, int key) {
- if (root == nullptr) {
- return { nullptr, nullptr };
- }
- if (getx(root->l) <= key) {
- auto splitted = split(root->r, key - getx(root->l) - 1);
- root->r = splitted.first;
- upd(root);
- return { root, splitted.second };
- }
- else {
- auto splitted = split(root->l, key);
- root->l = splitted.second;
- upd(root);
- return { splitted.first, root };
- }
- }
- node* merge(node* left, node* right) {
- if (left == nullptr || right == nullptr) {
- return right != nullptr ? right : left;
- }
- if (left->y > right->y) {
- left->r = merge(left->r, right);
- upd(left);
- return left;
- }
- else {
- right->l = merge(left, right->l);
- upd(right);
- return right;
- }
- }
- int type = 0;
- void erase(node*& root, int key) {
- }
- void insert(node *&root, int key) {
- }*/
- vector<pii> g[N];
- int dp[N][505];
- set<int> is;
- int k;
- int n, m, start, endd;
- void bfs() {
- priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
- q.push({ 0, { start, k } });
- dp[start][k] = 0;
- while (q.size()) {
- int cnt = q.top().second.second; // текущее кол-во энергии
- int u = q.top().second.first; // текущий город
- int c = q.top().first; // текущее кол-во использованных заправок
- q.pop();
- if (c != dp[u][cnt]) continue;
- for (auto to : g[u]) {
- int v = to.first;
- int len = to.second;
- if (len > k) continue;
- if (cnt - len < 0) {
- if (is.find(u) != is.end()) { // если в городе, где мы находимся, есть заправка
- if (c + 1 < dp[v][k - len]) {
- dp[v][k - len] = c + 1;
- q.push({ c + 1, { v, k - len } });
- }
- }
- }
- else {
- if (c < dp[v][cnt - len]) {
- dp[v][cnt - len] = c;
- q.push({ c, { v, cnt - len } });
- }
- if (is.find(u) != is.end()) { // если в городе, где мы находимся, есть заправка
- if (c + 1 < dp[v][k - len]) {
- dp[v][k - len] = c + 1;
- q.push({ c + 1 , { v, k - len } });
- }
- }
- }
- }
- }
- }
- signed main() {
- #ifndef ONLINE_JUDGE
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #else
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> k;
- cin >> n >> m >> start >> endd;
- while (m--) {
- int a, b, val;
- cin >> a >> b >> val;
- g[a].pb({ b, val });
- g[b].pb({ a, val });
- }
- for (int i = 0; i < 505; ++i) {
- fill(dp[i], dp[i] + 505, INF);
- }
- int l;
- cin >> l;
- while (l--) {
- int x;
- cin >> x;
- is.insert(x);
- }
- bfs();
- int mn = INF;
- for (int i = 0; i <= k; ++i) {
- mn = min(dp[endd][i], mn);
- }
- if (mn == INF) {
- cout << -1 << endl;
- }
- else {
- cout << mn << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement