Guest User

Untitled

a guest
Jan 19th, 2018
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #pragma comment (linker, "/STACK:64000000")
  2. #include <fstream>
  3. #include <vector>
  4. #include <stack>
  5. #include <cstdio>
  6.  
  7. using namespace std;
  8.  
  9. struct edje_to
  10. {
  11.     int to;
  12.     int weght;
  13. };
  14.  
  15. vector<edje_to>* edjes;
  16. vector<int> nodes;
  17. int* colors;
  18. int* weights;
  19.  
  20. int m, n;
  21. int a, b;
  22. int s, t;
  23. edje_to p;
  24. bool path = false;
  25.  
  26. void topsort(int v)
  27. {
  28.     colors[v] = 1;
  29.     for (int i = 0; i < edjes[v].size(); i++)
  30.     {
  31.         if (colors[edjes[v][i].to] == 0)
  32.         {
  33.             topsort(edjes[v][i].to);
  34.         }
  35.     }
  36.     colors[v] = 2;
  37.     nodes.push_back(v);
  38. }
  39.  
  40. int main()
  41. {
  42.     ifstream in;
  43.     ofstream out;
  44.  
  45.     in.open("shortpath.in");
  46.         in >> n >> m >> s >> t;
  47.         edjes = new vector<edje_to> [n];
  48.         colors = new int [n];
  49.         weights = new int [n];
  50.         for (int i = 0; i < n; i++)
  51.         {
  52.             colors[i] = 0;
  53.             weights[i] = 2100000000;
  54.         }
  55.         for (int i = 0; i < m; i++)
  56.         {
  57.             in >> a >> p.to >> p.weght;
  58.             p.to--;
  59.             edjes[a - 1].push_back(p);
  60.         }
  61.     in.close();
  62.  
  63.     for(int i = 0; i < n; i++)
  64.     {
  65.         if(colors[i] == 0)
  66.         {
  67.             topsort(i);
  68.         }
  69.     }
  70.  
  71.     a = 0;
  72.  
  73.     for(int i = nodes.size() - 1; i > 0; i--)
  74.     {
  75.         if(nodes[i] == s - 1)
  76.         {
  77.             a = i;
  78.             break;
  79.         }
  80.     }
  81.  
  82.     weights[s - 1] = 0;
  83.     for(int i = a; i >= 0; i--)
  84.     {
  85.         for(int j = 0; j < edjes[nodes[i]].size(); j++)
  86.         {
  87.             if(weights[edjes[nodes[i]][j].to] > weights[nodes[i]] + edjes[nodes[i]][j].weght)
  88.             {
  89.                 weights[edjes[nodes[i]][j].to] = weights[nodes[i]] + edjes[nodes[i]][j].weght;
  90.             }
  91.         }
  92.     }
  93.  
  94.     out.open("shortpath.out");
  95.         if(weights[t - 1] == 2100000000)
  96.         {
  97.             out << "Unreachable";
  98.         }
  99.         else
  100.         {
  101.             out << weights[t - 1];
  102.         }
  103.     out.close();
  104.  
  105.     return 0;
  106. }
Add Comment
Please, Sign In to add comment