Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- vector <pair<int, int> > d;
- vector <pair<int, int> > g[101000];
- int q[101000];
- int const INF = 100000000;
- void siftup(int i)
- {
- while (i > 0 && d[i].first < d[i / 2].first) {
- swap(d[i], d[i / 2]);
- i /= 2;
- }
- }
- void in(int x, int y)
- {
- d.push_back(make_pair(x, y));
- siftup(x);
- }
- void siftdown(int i)
- {
- while (2 * i < d.size()) {
- int j = i;
- if (d[2 * i] < d[j])
- j = 2 * i;
- if (2 * i + 1 < d.size() && d[2 * i + 1] < d[j])
- j = 2 * i + 1;
- if (i == j)
- break;
- swap(d[i], d[j]);
- i = j;
- }
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, m, x, y, c;
- cin >> n >> m;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++) {
- cin >> x >> y >> c;
- if (x != y)
- continue;
- g[x].push_back(make_pair(y, c));
- g[y].push_back(make_pair(x, c));
- }
- for (int i = 0; i < n; i++)
- q[i] = INF;
- int a, b;
- cin >> a >> b;
- in(0, a - 1);
- for (int i = 0; i < g[a - 1].size(); i++) {
- in(g[a - 1][i].first, g[a - 1][i].second);
- q[g[a - 1][i].second] = g[a - 1][i].first;
- }
- for (int i = 0; i < n - 1; i++) {
- x = d[0].first;
- y = d[0].second;
- int n1 = d.size();
- d[0] = d[n1 - 1];
- d.resize(n1 - 1);
- siftdown(0);
- for (int j = 0; j < g[y].size(); j++) {
- int x1 = g[y][j].first, y1 = g[y][j].second;
- cout << x << ' ' << y << ' ' << q[x1] << ' ' << x1 << ' ' << y1 << endl;
- if (q[x1] > x + y1) {
- q[x1] = x + y1;
- in(q[x1], x1);
- }
- }
- }
- cout << q[b - 1] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement