Guest User

Untitled

a guest
Jan 19th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <fstream>
  2. #include <cstdio>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. vector<int> tsort;
  7.  
  8. int n, m;
  9. int s,t;
  10. int v1, v2, v3;
  11. vector<pair<int, int>> *arr;   
  12. bool* visited;
  13.  
  14.  
  15. void dfs(int i)
  16. {  
  17.     visited[i] = true;
  18.     for(size_t j = 0; j < arr[i].size(); j++)
  19.         if (!visited[arr[i][j].first])
  20.             dfs(arr[i][j].first);
  21.  
  22.     tsort.push_back(i);    
  23. }
  24.  
  25. int main()
  26. {
  27.     ifstream in("shortpath.in");
  28.     ofstream out("shortpath.out");
  29.  
  30.     in >> n >> m >> s >> t;
  31.  
  32.     --s;
  33.     --t;
  34.     visited = new bool [n];
  35.     arr = new vector<pair<int,int>> [n];
  36.     for (int i = 0; i < n; i++)
  37.     {  
  38.         visited[i] = false;;   
  39.     }
  40.  
  41.     pair<int, int> p;
  42.     for(int i = 0; i < m; i++)
  43.     {
  44.         in >> v1 >> v2 >> v3;
  45.         v1--;
  46.         v2--;
  47.         p.first = v2;
  48.         p.second = v3;
  49.         arr[v1].push_back(p);
  50.     }
  51.  
  52.     for(int i = 0; i < n; i++)
  53.         if(!visited[i])
  54.             dfs(i);
  55.    
  56.    
  57.     int v;
  58.     int *d;
  59.     d = new int [n];
  60.     for (int i = 0; i < n; i++)
  61.         d[i] = 1001;
  62.     d[s] = 0;
  63.     for(int i = (n - 1); i >= 0 ; i--)
  64.     {
  65.         v = tsort[i];
  66.         if (d[v] == 1001) continue;
  67.  
  68.         for (size_t j = 0; j < arr[v].size(); j++)
  69.             d[arr[v][j].first] = min(d[arr[v][j].first],d[v] + arr[v][j].second);      
  70.  
  71.     }
  72.  
  73.     if(d[t] == 1001)
  74.         out << "Unreachable";
  75.     else
  76.         out << d[t];
  77. }
Add Comment
Please, Sign In to add comment