Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <string>
- #include <vector>
- #define MAX(a, b) ((a) > (b) ? (a) : (b))
- #define MIN(a, b) ((a) < (b) ? (a) : (b))
- #define __PAUSE system("pause");
- #define VEC std::vector <
- #define QUE std::queue <
- #define SET std::set <
- #define PAIR std::pair <
- #define in std::cin
- #define out std::cout
- typedef long long ll;
- /*
- struct set_struct {
- ll marked = 0;
- ll set_vertex;
- }; // set data
- */
- struct list_struct {
- ll vertex;
- ll len_to_v;
- }; // list data
- VEC VEC list_struct >> gr;
- VEC ll > dist;
- ll n, m;
- int main() {
- ll start, f;
- in >> n >> start >> f;
- start--;
- f--;
- gr.resize(n);
- dist.resize(n, 1e9);
- for (ll i = 0; i < n; i++) {
- for (ll j = 0; j < n; j++) {
- static ll x;
- in >> x;
- if (x != -1) gr[i].push_back({j, x});
- }
- }
- dist[start] = 0;
- SET PAIR ll, ll>> s;
- s.insert({0, start});
- while (!s.empty()) {
- ll v = s.begin()->second;
- s.erase(s.begin());
- for (auto p : gr[v]) {
- ll u = p.vertex, w = p.len_to_v;
- if (dist[u] > dist[v] + w) {
- s.erase({dist[u], u});
- dist[u] = dist[v] + w;
- s.insert({dist[u], u});
- }
- }
- }
- if (dist[f] == 1e9) {
- out << -1;
- __PAUSE
- return 0;
- }
- out << dist[f] << "\n";
- __PAUSE
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement