Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- vector<vector<pair<int, int>>> g;
- const int inf = 1e12;
- main()
- {
- #ifdef _DEBUG
- freopen("in.txt","rt",stdin);
- #endif // _DEBUG
- int n, s, f;
- cin >> n >> s >> f;
- s--, f--;
- g.resize(n);
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- int t;
- scanf("%lld", &t);
- if (t != -1 && (i != j))
- g[i].push_back({j, t});
- }
- }
- vector<bool> used(n, false);
- vector<int> d(n, inf);
- d[s] = 0;
- for (int i = 0; i < n; i++)
- {
- int v = -1;
- for (int j = 0; j < n; j++)
- if (!used[j] && (v == -1 || d[j] < d[v]))
- v = j;
- if (d[v] == inf)
- break;
- used[v] = true;
- for (int j = 0; j < g[v].size(); j++)
- {
- int to = g[v][j].first;
- int len = g[v][j].second;
- if (d[v] + len < d[to])
- d[to] = d[v] + len;
- }
- }
- if (d[f] == inf)
- cout << -1;
- else
- cout << d[f];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement