Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #include <vector>
- #include <algorithm>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define x first
- #define y second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- //#define FOR(i,a,b) for (int i = (a); i < (b); i++)
- //#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- const int INF = 1e9 * 2;
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n, m;
- cin >> n;
- vector<int> cost(n);
- for (int i = 0; i < n; i++) cin >> cost[i];
- cin >> m;
- vector<vector<bool>> vec(n, vector<bool>(n));
- for (int i = 0; i < m; i++) {
- int a, b; cin >> a >> b;
- vec[--a][--b] = true;
- vec[b][a] = true;
- }
- vector<vector<int>> d(n, vector<int>{INF, INF});
- d[0] = { 0, cost[0] };
- vector<vector<bool>> used(n, vector<bool>(2));
- for (int i = 0; i < 2 * n; i++) {
- pi v = mp(-1, -1);
- for (int j = 0; j < n; j++)
- for (int k = 0; k < 2; k++)
- if (!used[j][k] && (v == mp(-1, -1) || d[j][k] < d[v.x][v.y])) {
- v.x = j, v.y = k;
- }
- if (d[v.x][v.y] == INF)
- break;
- used[v.x][v.y] = true;
- for (int j = 0; j < n; j++)
- if (vec[v.x][j]) {
- if (v.y) {
- d[j][0] = min(d[j][0], d[v.x][1]);
- d[j][1] = min(d[j][1], d[v.x][1] + cost[v.x]);
- }
- else {
- d[j][0] = min(d[j][0], d[v.x][0] + cost[v.x]);
- d[j][1] = min(d[j][1], d[v.x][0] + 2 * cost[v.x]);
- }
- }
- }
- cout << (d[n - 1][0] == INF ? -1 : d[n-1][0]) << "\n";
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement