From BARBUT-DICA, 4 Days ago, written in C++.
Embed
  1. #include <fstream>
  2. #include <vector>
  3. #include <queue>
  4. #include <utility>
  5. #include <algorithm>
  6. #include <functional>
  7.  
  8. #define OO 0x3f3f3f3f
  9. using smart_pair = std::pair <int, std::pair <int, int>>;
  10.  
  11.  
  12. std::ifstream fin ("dragoni.in");
  13. std::ofstream fout ("dragoni.out");
  14.  
  15. int task, n, m;
  16. std::vector <std::vector <std::pair <int, int>>> Graph;
  17. std::vector <int> Dmax;
  18.  
  19.  
  20. inline int Go_PathFinder (int src)
  21. {
  22.     int max_dist = Dmax[src];
  23.     std::vector <int> Seen (n + 1, false);
  24.     std::queue <int> Q;
  25.  
  26.     Q.push (src); Seen[src] = true;
  27.  
  28.     while (!Q.empty ())
  29.     {
  30.         int v = Q.front (); Q.pop ();
  31.  
  32.         for (auto it : Graph[v])
  33.         {
  34.             if (!Seen[it.first] && it.second <= Dmax[src])
  35.             {
  36.                 Q.push (it.first); Seen[it.first] = true;
  37.                 max_dist = std::max (max_dist, Dmax[it.first]);
  38.             }
  39.         }
  40.     }
  41.  
  42.     return max_dist;
  43. }
  44.  
  45.  
  46. inline int Go_Dijkstra (int src, int dest)
  47. {
  48.     std::vector <int> Distance (n * n + 1, OO);
  49.     std::priority_queue <smart_pair, std::vector <smart_pair>, std::greater <smart_pair>> Q;
  50.  
  51.     Distance[src] = 0; Q.push (std::make_pair (Distance[src], std::make_pair (src, src)));
  52.  
  53.     while (!Q.empty ())
  54.     {
  55.         smart_pair p = Q.top (); Q.pop ();
  56.         fout << "\t" << p.first << " " << p.second.first << " " << p.second.second << "\n";
  57.  
  58.         for (auto it : Graph[p.second.first])
  59.         {
  60.             fout << "\t\t" << it.first << " " << it.second << "\n";
  61.             if (it.second <= Dmax[p.second.second] &&
  62.                 Distance[it.first + (p.second.second - 1) * n] > Distance[p.second.first + (p.second.second - 1) * n] + it.second)
  63.             {
  64.                 Distance[it.first + (p.second.second - 1) * n] = Distance[p.second.first + (p.second.second - 1) * n] + it.second;
  65.                 fout << it.first + (p.second.second - 1) * n << ": " << Distance[it.first + (p.second.second - 1) * n] << "\n";
  66.                 Q.push (std::make_pair (Distance[it.first + (p.second.second - 1) * n], std::make_pair (it.first, p.second.second)));
  67.  
  68.                 if (p.second.first != p.second.second)
  69.                 {
  70.                     Distance[it.first + (it.first - 1) * n] = Distance[it.first + (p.second.second - 1) * n];
  71.                     Q.push (std::make_pair (Distance[it.first + (it.first - 1) * n], std::make_pair (it.first, it.first)));
  72.                 }
  73.             }
  74.         }
  75.     }
  76.  
  77.     fout << "\n";
  78.     for (int i = 1; i <= n * n; ++ i)
  79.         fout << Distance[i] << " ";
  80.     fout << "\n";
  81.  
  82.     int min_dist = Distance[(n - 1) * n + 1];
  83.     for (int i = (n - 1) * n + 1; i <= n * n; ++ i)
  84.         min_dist = std::min (min_dist, Distance[i]);
  85.  
  86.     return min_dist;
  87. }
  88.  
  89.  
  90. int main ()
  91. {
  92.     fin >> task >> n >> m;
  93.  
  94.     Graph = std::vector <std::vector <std::pair <int, int>>> (n + 1);
  95.     Dmax = std::vector <int> (n + 1, 0);
  96.  
  97.     for (int i = 1; i <= n; ++ i)
  98.         fin >> Dmax[i];
  99.  
  100.     for (int i = 1, u, v, d; i <= m; ++ i)
  101.     {
  102.         fin >> u >> v >> d;
  103.  
  104.         Graph[u].push_back (std::make_pair (v, d));
  105.         Graph[v].push_back (std::make_pair (u, d));
  106.     }
  107.     fin.close ();
  108.  
  109.  
  110.     if (task == 1)
  111.     {
  112.         fout << Go_PathFinder (1);
  113.     }
  114.     else
  115.     {
  116.         fout << "\n" << Go_Dijkstra (1, n);
  117.     }
  118.     fout.close ();
  119.  
  120.     return 0;
  121. }
  122.