Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:640000000")
- #include<iostream>
- #include<fstream>
- #include<cstdio>
- #include<cassert>
- #include<cstring>
- #include<ctime>
- #include<cstdlib>
- #include<cmath>
- #include<string>
- #include<sstream>
- #include<map>
- #include<set>
- #include<queue>
- #include<stack>
- #include<vector>
- #include<bitset>
- #include<algorithm>
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define all(x) (x).begin(),(x).end()
- #define sz(x) (int)(x).size()
- #define ll long long
- #define bit __builtin_popcountll
- #define sqr(x) (x) * (x)
- #define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++)
- #define debug(x) cout << #x <<" = " << x << endl
- #define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
- using namespace std;
- typedef pair<int, int> pii;
- const double eps = 1e-9;
- const double pi = acos(-1.0);
- const int INF = 1000000000;
- const int N = 101;
- int n,s,f,
- a[N][N];
- int main() {
- ios_base::sync_with_stdio(0);
- cin >> n >> s >> f;
- forn(i,n) forn(j,n) cin >> a[i][j];
- vector<int> d (n, INF), p(n);
- d[s] = 0;
- vector<char> used(n);
- forn (i,n) {
- int v = -1;
- forn (j,n)
- if (!used[j] && (v == -1 || d[j] < d[v]))
- v = j;
- if (d[v] == INF)
- break;
- used[v] = true;
- forn (j,n){
- if (a[v][j] > 0){
- int to = j,
- len = a[v][j];
- if (d[v] + len < d[to]){
- d[to] = d[v] + len;
- }
- }
- }
- }
- if (d[f] == INF) {
- cout << -1 << endl;
- return 0;
- }
- cout << d[f] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement