Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int MAX = 2005;
- const long long INF = 9223372036854775807;
- int n, m, start, finish, v;
- long long w[MAX][MAX], d[MAX];
- bool used[MAX];
- void initialize(){
- for(int i = 0; i < n; i++)
- d[i] = INF;
- }
- int nextVertex(){
- int minV = -1;
- for(int i = 0; i < n; i++)
- if(!used[i] && (minV == -1 || d[i] < d[minV]))
- minV = i;
- return minV;
- }
- void dijkstra(int s){
- initialize();
- d[start] = 0;
- while((v = nextVertex()) != -1){
- used[v] = true;
- for(int i = 0; i < n; i++){
- long e = w[v][i];
- if(e == -1 || i == v)
- continue;
- if(d[i] > d[v] + e)
- d[i] = d[v] + e;
- }
- }
- }
- int main()
- {
- freopen ("pathmgep.in", "r", stdin);
- freopen ("pathmgep.out" ,"w", stdout);
- scanf("%d%d%d", &n, &start, &finish);
- start--, finish--;
- for(int i = 0; i < n; i++)
- for(int j = 0; j < n; j++)
- scanf("%d", &w[i][j]);
- dijkstra(start);
- if(d[finish] == INF)
- cout << "-1" << endl;
- else
- cout << d[finish] << endl;;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement