Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2014
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. vector <pair<int, int> > d;
  8. vector <pair<int, int> > g[101000];
  9. int q[101000];
  10. int const INF = 100000000;
  11.  
  12. void siftup(int i)
  13. {
  14.     while (i > 0 && d[i].first < d[i / 2].first) {
  15.         swap(d[i], d[i / 2]);
  16.         i /= 2;
  17.     }
  18. }
  19.  
  20. void in(int x, int y)
  21. {
  22.     d.push_back(make_pair(x, y));
  23.     siftup(x);
  24. }
  25.  
  26. void siftdown(int i)
  27. {
  28.     while (2 * i < d.size()) {
  29.         int j = i;
  30.         if (d[2 * i] < d[j])
  31.             j = 2 * i;
  32.         if (2 * i + 1 < d.size() && d[2 * i + 1] < d[j])
  33.             j = 2 * i + 1;
  34.         if (i == j)
  35.             break;
  36.         swap(d[i], d[j]);
  37.         i = j;
  38.     }
  39. }
  40.  
  41. int main()
  42. {
  43.     freopen("input.txt", "r", stdin);
  44.     freopen("output.txt", "w", stdout);
  45.     int n, m, x, y, c;
  46.     cin >> n >> m;
  47.     for (int i = 0; i < n; i++)
  48.         for (int j = 0; j < m; j++) {
  49.             cin >> x >> y >> c;
  50.             if (x != y)
  51.                 continue;
  52.             g[x].push_back(make_pair(y, c));
  53.             g[y].push_back(make_pair(x, c));
  54.         }
  55.     for (int i = 0; i < n; i++)
  56.         q[i] = INF;
  57.     int a, b;
  58.     cin >> a >> b;
  59.     in(0, a - 1);
  60.     for (int i = 0; i < g[a - 1].size(); i++) {
  61.         in(g[a - 1][i].first, g[a - 1][i].second);
  62.         q[g[a - 1][i].second] = g[a - 1][i].first;
  63.     }
  64.     for (int i = 0; i < n - 1; i++) {
  65.         x = d[0].first;
  66.         y = d[0].second;
  67.         int n1 = d.size();
  68.         d[0] = d[n1 - 1];
  69.         d.resize(n1 - 1);
  70.         siftdown(0);
  71.         for (int j = 0; j < g[y].size(); j++) {
  72.             int x1 = g[y][j].first, y1 = g[y][j].second;
  73.             cout << x << ' ' << y << ' ' << q[x1] << ' ' << x1 << ' ' << y1 << endl;
  74.             if (q[x1] > x + y1) {
  75.                 q[x1] = x + y1;
  76.                 in(q[x1], x1);
  77.             }
  78.         }
  79.     }
  80.     cout << q[b - 1] << endl;
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement