SHARE
TWEET

Untitled

a guest Feb 28th, 2020 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define INF 1e9
  3.  
  4. using namespace std;
  5.  
  6. int g[111][111] , M[111] , d[111];
  7. priority_queue<pair <int , int> , vector<pair<int , int> >, greater<pair <int , int> >> q;
  8. int main() {
  9.     int n , s , f;
  10.     cin >> n >> s >> f;
  11.     for (int i = 1; i <= n; i++) {
  12.         for (int j = 1; j <= n; j++) {
  13.             cin >> g[i][j];
  14.             if (g[i][j] == -1) {
  15.                 g[i][j] = INF;
  16.             }
  17.         }
  18.     }
  19.     for (int i = 1; i <= n; i++) {
  20.         d[i] = g[s][i];
  21.         if (!(s == i)) q.push({d[i] , i});
  22.     }
  23.     M[s] = 1;
  24.     for (int i = 2; i <= n; i++) {
  25.         while (M[q.top().second] == 1) {
  26.             if (q.empty()) {
  27.                 break;
  28.             }
  29.             q.pop();
  30.         }
  31.         int mn = q.top().first , v = q.top().second;
  32.         M[v] = 1;
  33.         for (int j = 1; j <= n; j++) {
  34.             if (M[j] == 0 && d[j] > d[v] + g[v][j]) {
  35.                 d[j] = d[v] + g[v][j];
  36.                 q.push({d[j] , j});
  37.             }
  38.         }
  39.     }
  40.     if (d[f] != INF) {
  41.         cout << d[f];
  42.     } else {
  43.         cout << -1;
  44.     }
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top