Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define INF 1e9
- using namespace std;
- int g[111][111] , M[111] , d[111];
- priority_queue<pair <int , int> , vector<pair<int , int> >, greater<pair <int , int> >> q;
- int main() {
- int n , s , f;
- cin >> n >> s >> f;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- cin >> g[i][j];
- if (g[i][j] == -1) {
- g[i][j] = INF;
- }
- }
- }
- for (int i = 1; i <= n; i++) {
- d[i] = g[s][i];
- if (!(s == i)) q.push({d[i] , i});
- }
- M[s] = 1;
- for (int i = 2; i <= n; i++) {
- while (M[q.top().second] == 1) {
- if (q.empty()) {
- break;
- }
- q.pop();
- }
- int mn = q.top().first , v = q.top().second;
- M[v] = 1;
- for (int j = 1; j <= n; j++) {
- if (M[j] == 0 && d[j] > d[v] + g[v][j]) {
- d[j] = d[v] + g[v][j];
- q.push({d[j] , j});
- }
- }
- }
- if (d[f] != INF) {
- cout << d[f];
- } else {
- cout << -1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement