-
Notifications
You must be signed in to change notification settings - Fork 1
/
algorithm.cpp
78 lines (65 loc) · 1.67 KB
/
algorithm.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <limits>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using Graph = boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::directedS,
boost::no_property,
boost::property<boost::edge_weight_t, int>
>;
void testcase() {
int n, m, k , t; std::cin >> n >> m >> k >> t;
Graph g(2 * n);
std::vector<int> tp(n);
for (int i = 0; i < t; i++){
int x; std::cin >> x;
tp[i] = x;
}
for (int i = 0; i < m; i++) {
int u, v, c; std::cin >> u >> v >> c;
boost::add_edge(v, u, c, g);
}
std::vector<int> scc(2 * n);
int scc_count = boost::strong_components(
g,
boost::make_iterator_property_map(scc.begin(), boost::get(boost::vertex_index, g))
);
std::vector<std::vector<int>> subnets(scc_count);
for (int i = 0; i < t; i++)
subnets[scc[tp[i]]].push_back(tp[i]);
for (int i = 0; i < scc_count; i++) {
for (const auto src: subnets[i]) {
boost::add_edge(n + i, src, 0, g);
boost::add_edge(src, n + i, subnets[i].size() - 1, g);
}
}
std::vector<int> dists(2 * n);
boost::dijkstra_shortest_paths(
g,
n - 1,
boost::distance_map(boost::make_iterator_property_map(dists.begin(), boost::get(boost::vertex_index, g)))
);
int min = 1000001;
for (int i = 0; i < k; i++)
min = std::min(min, dists[i]);
if (min < 1000001)
std::cout << min << std::endl;
else
std::cout << "no" << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
int t;
std::cin >> t;
for (int i = 0; i < t; ++i)
testcase();
}