Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <climits>
- #include <functional>
- #include <iostream>
- #include <set>
- #include <queue>
- #include <vector>
- #include <unordered_map>
- struct Vertex {
- public:
- int number, path_length;
- Vertex(){};
- Vertex(int v, int p) {
- number = v;
- path_length = p;
- }
- bool operator<(const Vertex &other) const {
- return path_length < other.path_length;
- }
- };
- class Graph {
- private:
- int vertices_number, source, target;
- std::unordered_map<int, std::unordered_map<int, int>> forward_graph;
- std::unordered_map<int, std::unordered_map<int, int>> backward_graph;
- public:
- bool path_exists = false;
- Graph() {};
- Graph(int n) {
- vertices_number = n;
- }
- void init_s_t(int s, int t) {
- source = s;
- target = t;
- }
- void add_edge(int from, int to, int weight) {
- forward_graph[from][to] = weight;
- backward_graph[to][from] = weight;
- }
- std::vector<long long> dijkstra(bool forward, int d) {
- std::vector<long long> dist(vertices_number, UINT_MAX);
- std::vector<bool> closed(vertices_number, false);
- std::set<Vertex> vertices_to_add;
- (forward ? dist[source] = 0 : dist[target] = 0);
- (forward ? vertices_to_add.insert(Vertex(source, 0)) : vertices_to_add.insert(Vertex(target, 0)));
- for (long long i = 0; i != vertices_number; ++i) {
- // pick new vertex
- if (vertices_to_add.empty()) break;
- Vertex shortest_vertex = *vertices_to_add.begin();
- vertices_to_add.erase(vertices_to_add.begin());
- if (forward && shortest_vertex.number == target) {
- path_exists = true;
- break;
- }
- closed[shortest_vertex.number] = true;
- if (dist[shortest_vertex.number] >= d) break;
- // update new neighbours values
- for (auto neighbour : (forward ? forward_graph[shortest_vertex.number] : backward_graph[shortest_vertex.number])) {
- // neighbour - map element: neighbour.first = vertex_number, neighbour.second = edge_weight
- if (!closed[neighbour.first]) {
- // std::cout << "Processing neighbour " << neighbour.first << std::endl;
- if ((dist[shortest_vertex.number] + neighbour.second < dist[neighbour.first]) && (dist[neighbour.first] != UINT_MAX)) {
- vertices_to_add.erase(Vertex(neighbour.first, dist[neighbour.first]));
- }
- dist[neighbour.first] = dist[shortest_vertex.number] + neighbour.second;
- vertices_to_add.insert(Vertex(neighbour.first, dist[neighbour.first]));
- }
- } }
- return dist;
- }
- };
- int main () {
- int n, m, from, to, weight, s, t, d;
- long long res = 0;
- std::cin >> n >> m;
- Graph graph(n);
- for (long long i = 0; i < m; ++i) {
- std::cin >> from >> to >> weight;
- graph.add_edge(from - 1, to - 1, weight);
- }
- std::cin >> s >> t >> d;
- graph.init_s_t(s - 1, t - 1);
- std::vector<long long> forward_candidates;
- forward_candidates = graph.dijkstra(true, d);
- if (graph.path_exists) {
- std::cout << n * (n - 1) << std::endl;
- return 0;
- }
- std::vector<long long> backward_candidates;
- backward_candidates = graph.dijkstra(false, d);
- for (long long i = 0; i != forward_candidates.size(); ++i) {
- for (long long j = 0; j != backward_candidates.size(); ++j) {
- if (forward_candidates[i] == UINT_MAX || backward_candidates[j] == UINT_MAX) {
- continue;
- }
- if (forward_candidates[i] + backward_candidates[j] + 1 <= d) {
- // std::cout << i << ' ' << j << std::endl;
- res++;
- }
- }
- }
- std::cout << res << std::endl;
- }
- // int art = 0;
- // for (long long i = 0; i != forward_candidates.size(); ++i) {
- // std::cout << forward_candidates[i] << ' ';
- // if (forward_candidates[i] <= d - 1) {
- // // art++;
- // }
- // }
- // // std::cout << std::endl << "art: " << art << std::endl;
- // // int cnt = 0;
- // for (long long i = 0; i != backward_candidates.size(); ++i) {
- // std::cout << backward_candidates[i] << ' ';
- // if (backward_candidates[i] <= d - 1) {
- // // cnt++;
- // }
- // }
- // std::cout << std::endl << "cnt: " << cnt << std::endl;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement