fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. const uint32_t INF = INT32_MAX;
  7.  
  8. // void PrintGraph(std::vector<std::vector<std::pair<uint32_t, uint32_t>>> graph) {
  9. //     for (int i = 0; i < graph.size(); ++i) {
  10. //         std::cout << i << " : ";
  11. //         for (int  j = 0; j < graph[i].size(); ++j) {
  12. //             std::cout << graph[i][j].first << " : w = " << graph[i][j].second << ", ";
  13. //         }
  14. //         std::cout << "\n";
  15. //     }
  16. // }
  17.  
  18. std::vector<std::vector<std::pair<uint32_t, uint32_t>>> ReverseGraph(std::vector<std::vector<std::pair<uint32_t, uint32_t>>> graph) {
  19.     std::vector<std::vector<std::pair<uint32_t, uint32_t>>> graphR(graph.size());
  20.     for (uint32_t i = 0; i < graph.size(); ++i) {
  21.         for (uint32_t  j = 0; j < graph[i].size(); ++j) {
  22.             graphR[graph[i][j].first].push_back(std::make_pair(i, graph[i][j].second));
  23.         }
  24.     }
  25.  
  26.     return graphR;
  27. }
  28.  
  29. void InitializeSingleSource(uint32_t source, std::vector<uint32_t> &distances) {
  30.     for (uint32_t i = 0; i < distances.size(); ++i) {
  31.         distances[i] = INF;
  32.     }
  33.     distances[source] = 0;
  34. }
  35.  
  36. void Relax(uint32_t u, uint32_t v, uint32_t weight,
  37.            std::set<std::pair<uint32_t, uint32_t>> &q,
  38.            std::vector<uint32_t> &distances) {
  39.     if (distances[v] > distances[u] + weight) {
  40.         q.erase(std::make_pair(distances[v], v));
  41. 		distances[v] = distances[u] + weight;
  42. 		q.insert(std::make_pair(distances[v], v));
  43.     }
  44. }
  45.  
  46. void Dijkstra(std::vector<std::vector<std::pair<uint32_t, uint32_t>>> graph,
  47.               std::vector<uint32_t> &distances,
  48.               uint32_t source) {
  49.     InitializeSingleSource(source, distances);
  50.  
  51.     std::set<std::pair<uint32_t, uint32_t>> q;
  52.     for (uint32_t i = 0; i < graph.size(); ++i) {
  53.         q.insert(std::make_pair(distances[i], i));
  54.     }
  55.  
  56.     uint32_t u, v;
  57.     uint32_t weight;
  58.     while (!q.empty()) {
  59.         u = q.begin()->second;
  60. 		q.erase(q.begin());
  61.  
  62.         for (uint32_t i = 0; i < graph[u].size(); ++i) {
  63.             v = graph[u][i].first;
  64.             weight = graph[u][i].second;
  65.             Relax(u, v, weight, q, distances);
  66. 		}
  67.     }
  68. }
  69.  
  70. struct ComparatorAsc {
  71. 	std::vector<uint32_t> values;
  72.     bool operator() (uint32_t i, uint32_t j) { 
  73. 	    return (values[i] < values[j]);
  74.     }
  75. };
  76.  
  77. struct ComparatorDesc {
  78. 	std::vector<uint32_t> values;
  79.     bool operator() (uint32_t i, uint32_t j) { 
  80. 	    return (values[i] > values[j]);
  81.     }
  82. };
  83.  
  84.  
  85. int main() {
  86.     uint32_t n, m;
  87.     std::cin >> n >> m;
  88.  
  89.     std::vector<std::vector<std::pair<uint32_t, uint32_t>>> graph(n);
  90.     std::vector<std::vector<std::pair<uint32_t, uint32_t>>> graphR(n);
  91.     std::vector<uint32_t> forwardDistances(n);
  92.     std::vector<uint32_t> backwardDistances(n);
  93.  
  94.     uint32_t u, v;
  95.     uint32_t weight;
  96.     for (uint32_t i = 0; i < m; ++i) {
  97.         std::cin >> u >> v >> weight;
  98.         graph[u - 1].push_back(std::make_pair(v - 1, weight));
  99.     }
  100.  
  101.     uint32_t s, t, d;
  102.     std::cin >> s >> t >> d;
  103.  
  104.     Dijkstra(graph, forwardDistances, s - 1);
  105.     graphR = ReverseGraph(graph);
  106.     Dijkstra(graphR, backwardDistances, t - 1);
  107.  
  108.     std::vector<uint32_t> forwardIndices(n);
  109.     std::vector<uint32_t> backwardIndices(n);
  110.     for (uint32_t i = 0; i < n; ++i) {
  111.         forwardIndices[i] = i;
  112.         backwardIndices[i] = i;
  113.     }
  114.  
  115.     uint64_t count = 0;
  116.     if (forwardDistances[t - 1] <= d) {
  117.         count = n*(n - 1);
  118.     } else {
  119.         ComparatorAsc forwardCompare;
  120.         ComparatorDesc backwardCompare;
  121.         forwardCompare.values = forwardDistances;
  122.         backwardCompare.values = backwardDistances;
  123.         std::sort(forwardIndices.begin(), forwardIndices.end(), forwardCompare);
  124.         std::sort(backwardIndices.begin(), backwardIndices.end(), backwardCompare);
  125.  
  126.         uint32_t j = 0;
  127.         for (uint32_t i = 0; i < n; ++i) {
  128.             while ((forwardDistances[forwardIndices[i]] + backwardDistances[backwardIndices[j]] >= d) && (j < n)) { 
  129.                 j += 1;
  130.             }
  131.             count += n - j;
  132.         }
  133.     }
  134.     std::cout << count;
  135.     return 0;
  136. }
  137.  
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
4 3
1 2 1
2 3 1
3 4 1
1 4 2
stdout
copy 
3
https://ideone.com/xVqW8f
language:
C++14 (clang 8.0)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!