Advertisement
savrasov

Untitled

Apr 13th, 2017
366
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string.h>
  4. #include <cstring>
  5. #include <math.h>
  6. #include <cmath>
  7. #include <vector>
  8. #include <utility>
  9. #include <cstdlib>
  10. #include <deque>
  11. #include <queue>
  12. #include <iomanip>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <cmath>
  17. #include <fstream>
  18. #include <list>
  19.  
  20. using namespace std;
  21.  
  22.  
  23. typedef long long ll;
  24. const ll INF = 1e18;
  25.  
  26. ll n, s = 0, f, b[220], m;
  27. vector <vector<pair<ll, ll> > > g(120);
  28. vector<ll> d(120, INF), p(120);
  29. set <pair<ll, ll> > q;
  30.  
  31.  
  32. int main() {
  33.     cin >> n;
  34.     f = n - 1;
  35.     for (int i = 0; i < n; i++)
  36.         cin >> b[i];
  37.     cin >> m;
  38.     for (int i = 0; i < m; i++)
  39.     {
  40.         int t, y;
  41.         cin >> t >> y;
  42.         t--; y--;
  43.         g[t].push_back(make_pair(y, b[t]));
  44.         g[y].push_back(make_pair(t, b[y]));
  45.     }
  46.     d[s] = 0;
  47.     q.insert(make_pair(d[s], s));
  48.     while (!q.empty()) {
  49.         int v = q.begin()->second;
  50.         q.erase(q.begin());
  51.         for (int j = 0; j < g[v].size(); ++j) {
  52.             int to = g[v][j].first,
  53.                 len = g[v][j].second;
  54.             if (d[v] + len < d[to]) {
  55.                 q.erase(make_pair(d[to], to));
  56.                 d[to] = d[v] + len;
  57.                 p[to] = v;
  58.                 q.insert(make_pair(d[to], to));
  59.             }
  60.         }
  61.     }
  62.     if(d[f] == INF)return cout << -1, 0;
  63.     else cout << d[f];
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement