Advertisement
Guest User

Untitled

a guest
Jul 1st, 2015
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:640000000")
  2. #include<iostream>
  3. #include<fstream>
  4. #include<cstdio>
  5. #include<cassert>
  6. #include<cstring>
  7. #include<ctime>
  8. #include<cstdlib>
  9. #include<cmath>
  10. #include<string>
  11. #include<sstream>
  12. #include<map>
  13. #include<set>
  14. #include<queue>
  15. #include<stack>
  16. #include<vector>
  17. #include<bitset>
  18. #include<algorithm>
  19.  
  20. #define pb push_back
  21. #define ppb pop_back
  22. #define mp make_pair
  23. #define all(x) (x).begin(),(x).end()
  24. #define sz(x) (int)(x).size()
  25. #define ll long long
  26. #define bit __builtin_popcountll
  27. #define sqr(x) (x) * (x)
  28. #define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++)
  29. #define debug(x) cout << #x <<" = " << x << endl
  30. #define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
  31.  
  32. using namespace std;
  33.  
  34. typedef pair<int, int> pii;
  35.  
  36. const double eps = 1e-9;
  37. const double pi = acos(-1.0);
  38. const int INF = 1000000000;
  39. const int N = 101;
  40. int n,s,f,
  41.    a[N][N];
  42. int main() {
  43.     ios_base::sync_with_stdio(0);
  44.        
  45.     cin >> n >> s >> f;
  46.    
  47.     forn(i,n) forn(j,n) cin >> a[i][j];
  48.    
  49.     vector<int> d (n, INF), p(n);
  50.     d[s] = 0;
  51.     vector<char> used(n);
  52.     forn (i,n) {
  53.         int v = -1;
  54.         forn (j,n)
  55.             if (!used[j] && (v == -1 || d[j] < d[v]))
  56.                 v = j;
  57.         if (d[v] == INF)
  58.             break;
  59.         used[v] = true;
  60.        
  61.         forn (j,n){
  62.             if (a[v][j] > 0){
  63.                 int to  = j,
  64.                     len = a[v][j];
  65.                 if (d[v] + len < d[to]){
  66.                     d[to] = d[v] + len;
  67.                 }      
  68.             }
  69.         }
  70.     }
  71.    
  72.     if (d[f] == INF) {
  73.         cout << -1 << endl;
  74.         return 0;
  75.     }
  76.     cout << d[f] << endl;
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement