fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. const int INF = 1000000;
  7.  
  8. void PrintGraph(std::vector<std::vector<std::pair<int, int>>> 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<int, int>>> ReverseGraph(std::vector<std::vector<std::pair<int, int>>> graph) {
  19.     std::vector<std::vector<std::pair<int, int>>> graphR(graph.size());
  20.     for (int i = 0; i < graph.size(); ++i) {
  21.         for (int  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(int source, std::vector<int> &distances, std::vector<int> &parents) {
  30.     for (int i = 0; i < distances.size(); ++i) {
  31.         distances[i] = INF;
  32.         parents[i] = -1;
  33.     }
  34.     distances[source] = 0;
  35. }
  36.  
  37. void Relax(int u, int v, int weight,
  38.            std::set<std::pair<int, int>> &q,
  39.            std::vector<int> &distances, std::vector<int> &parents) {
  40.     if (distances[v] > distances[u] + weight) {
  41.         q.erase(std::make_pair(distances[v], v));
  42. 		distances[v] = distances[u] + weight;
  43. 		parents[v] = u;
  44. 		q.insert(std::make_pair(distances[v], v));
  45.     }
  46. }
  47.  
  48. void Dijkstra(std::vector<std::vector<std::pair<int, int>>> graph,
  49.               std::vector<int> &distances, std::vector<int> &parents,
  50.               int source) {
  51.     InitializeSingleSource(source, distances, parents);
  52.  
  53.     std::set<std::pair<int, int>> q;
  54.     for (int i = 0; i < graph.size(); ++i) {
  55.         q.insert(std::make_pair(distances[i], i));
  56.     }
  57.  
  58.     int u, v;
  59.     int weight;
  60.     while (!q.empty()) {
  61.         u = q.begin()->second;
  62. 		q.erase(q.begin());
  63.  
  64.         // if (forwardDistances[uF] + backwardDistances[uB] >= Dmin) {
  65.         //     break;
  66.         // }
  67.  
  68.         for (int i = 0; i < graph[u].size(); ++i) {
  69.             v = graph[u][i].first;
  70.             weight = graph[u][i].second;
  71. 			// if (distances[v] > distances[u] + weight) {
  72. 			// 	q.erase(std::make_pair(distances[v], v));
  73. 			// 	distances[v] = distances[u] + weight;
  74. 			// 	parents[v] = u;
  75. 			// 	q.insert(std::make_pair(distances[v], v));
  76.             // }
  77.             Relax(u, v, weight, q, distances, parents);
  78. 		}
  79.     }
  80. }
  81.  
  82. struct ComparatorAsc {
  83. 	std::vector<int> values;
  84.     bool operator() (int i,int j) { 
  85. 	    return (values[i] < values[j]);
  86.     }
  87. };
  88.  
  89. struct ComparatorDesc {
  90. 	std::vector<int> values;
  91.     bool operator() (int i,int j) { 
  92. 	    return (values[i] > values[j]);
  93.     }
  94. };
  95.  
  96.  
  97. int main() {
  98.     int n, m;
  99.     std::cin >> n >> m;
  100.  
  101.     std::vector<std::vector<std::pair<int, int>>> graph(n);
  102.     std::vector<std::vector<std::pair<int, int>>> graphR(n);
  103.     std::vector<int> forwardDistances(n);
  104.     std::vector<int> backwardDistances(n);
  105.     std::vector<int> forwardParents(n);
  106.     std::vector<int> backwardParents(n);
  107.  
  108.     int u, v, weight;
  109.     for (int i = 0; i < m; ++i) {
  110.         std::cin >> u >> v >> weight;
  111.         graph[u - 1].push_back(std::make_pair(v - 1, weight));
  112.     }
  113.  
  114.     int s, t, d;
  115.     std::cin >> s >> t >> d;
  116.  
  117.     Dijkstra(graph, forwardDistances, forwardParents, s - 1);
  118.     graphR = ReverseGraph(graph);
  119.     Dijkstra(graphR, backwardDistances, backwardParents, t - 1);
  120.  
  121.     std::vector<int> forwardIndices(n);
  122.     std::vector<int> backwardIndices(n);
  123.     for (int i = 0; i < n; ++i) {
  124.         forwardIndices[i] = i;
  125.         backwardIndices[i] = i;
  126.     }
  127.  
  128.     long long count = 0;
  129.     if (forwardDistances[t - 1] <= d) {
  130.         count = n*(n - 1);
  131.     } else {
  132.         ComparatorAsc forwardCompare;
  133.         ComparatorDesc backwardCompare;
  134.         forwardCompare.values = forwardDistances;
  135.         backwardCompare.values = backwardDistances;
  136.         std::sort(forwardIndices.begin(), forwardIndices.end(), forwardCompare);
  137.         std::sort(backwardIndices.begin(), backwardIndices.end(), backwardCompare);
  138.  
  139.         int j = 0;
  140.         for (int i = 0; i < n; ++i) {
  141.             while ((forwardDistances[forwardIndices[i]] + backwardDistances[backwardIndices[j]] >= d) && (j < n)) { 
  142.                 j += 1;
  143.             }
  144.             count += n - j;
  145.         }
  146.     }
  147.     std::cout << count << "\n";
  148.     return 0;
  149. }
  150.  
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/xrYTBu
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!