artemgf

Российские газопроводы

Nov 9th, 2017
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include <iostream>
  3. #include <string>
  4. #include <map>
  5. #include <set>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <stdio.h>
  9. #include <cmath>
  10. #include <math.h>
  11. #include <queue>
  12. #include <stack>
  13. #include <climits>
  14. #include <deque>
  15. #include <ctime>
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long llu;
  21.  
  22. #define modulo pow(10,9)+7
  23. #define eps pow(10,-9)
  24. #define forn(i, n) for(int i = 0; i < n; ++i)
  25. #define rforn(i, n) for (int i = n; i >= 0; --i)
  26. #define files freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout)
  27. #define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  28. #define all(n) n.begin(), n.end()
  29. #define rall(n) n.rbegin(), n.rend()
  30.  
  31. vector<pair<int, int>> graf[501];
  32. int S[501];
  33.  
  34. void decs(int a)
  35. {
  36.     queue<int>next;
  37.     next.push(a);
  38.     S[a] = 0;
  39.     while (next.size() != 0)
  40.     {
  41.         int now = next.front();
  42.         next.pop();
  43.         for (int i = 0; i < graf[now].size(); i++)
  44.         {
  45.             if (S[graf[now][i].first] < S[now] + graf[now][i].second)
  46.             {
  47.                 S[graf[now][i].first] = S[now] + graf[now][i].second;
  48.                 next.push(graf[now][i].first);
  49.             }
  50.         }
  51.     }
  52. }
  53. int main()
  54. {
  55.     int n, m, a, b;
  56.     int prom, prom2, l;
  57.     cin >> n >> m;
  58.     for (int i = 1; i <= 500; i++)
  59.     {
  60.         S[i] = 0;
  61.     }
  62.     for (int i = 1; i <= m; i++)
  63.     {
  64.         cin >> prom >> prom2 >> l;
  65.         graf[prom].push_back({ prom2,l });
  66.     }
  67.     cin >> a >> b;
  68.     if (graf[a].size() != 0)
  69.     {
  70.         decs(a);
  71.         if (S[b] == 0 && b != a)
  72.         {
  73.             cout << "No solution";
  74.         }
  75.         else
  76.             cout << S[b];
  77.     }
  78.     else
  79.         cout << "No solution";
  80.     system("pause");
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment