#include<bits/stdc++.h>
using namespace std;
#define taskname "TEST"
#define pb push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
typedef pair<int,int> tpair;
#define mp make_pair
int n , m , k , q , a[maxn];
vector<tpair> adj[maxn];
set<int>* s[maxn];
int res[maxn] , d[maxn];
void enter()
{
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i)
{
int u , v , w;cin >> u >> v >> w;
adj[u].pb(mp(v,w));
adj[v].pb(mp(u,w));
}
cin >> k;
for(int i = 1 ; i <= k ; ++i)cin >> a[i];
}
priority_queue<tpair,vector<tpair>,greater<tpair>> pq;
void dij()
{
fill_n(d,maxn,(int)1e9);
for(int i = 1 ; i <= k ; ++i)
{
d[a[i]] = 0;
pq.push(mp(0,a[i]));
}
while(!pq.empty())
{
auto u = pq.top();pq.pop();
if(d[u.second] != u.first)continue;
for(auto c : adj[u.second])
{
if(d[c.first] > u.first + c.second)
{
d[c.first] = u.first + c.second;
pq.push(mp(d[c.first],c.first));
}
}
}
}
int lab[maxn];
int finds(int u)
{
return lab[u] < 0 ? u : lab[u] = finds(lab[u]);
}
void Uni(int now , int u , int v)
{
u = finds(u);
v = finds(v);
if(u == v)return;
if(lab[u] > lab[v])swap(u,v);
lab[u] += lab[v];
lab[v] = u;
if(s[u]->size() < s[v]->size())swap(s[u],s[v]);
for(auto c : (*s[v])){
if(s[u]->find(c) != s[u]->end())res[c] = min(res[c],now) , s[u]->erase(c);
else s[u]->insert(c);
}
s[v]->clear();
}
void solve()
{
cin >> q;
for(int i = 1 ; i <= n ; ++i)s[i] = new set<int>;
for(int i = 1 ; i <= q ; ++i)
{
int u , v;cin >> u >> v;
if(d[u] == 0 || d[v] == 0)
{
res[i] = 0;
continue;
}
// if(s[u] == NULL)s[u] = new set<int>;
res[i] = min(d[u],d[v]);
s[u]->insert(i);
s[v]->insert(i);
}
fill_n(lab,maxn,-1);
vector<tpair> v;
for(int i = 1 ; i <= n ; ++i)v.pb(mp(d[i],i));
sort(v.begin(),v.end(),greater<tpair>());
for(auto u : v)
{
for(auto c : adj[u.second])
if(d[c.first] >= u.first)Uni(u.first,u.second,c.first);
}
for(int i = 1 ; i <= q ; ++i)
cout << res[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r"))
freopen(taskname".INP", "r",stdin) ,
freopen(taskname".OUT", "w",stdout);
enter();
dij();
solve();
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:111:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin) ,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
freopen(taskname".OUT", "w",stdout);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:111:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3548 KB |
Output is correct |
2 |
Correct |
6 ms |
3704 KB |
Output is correct |
3 |
Correct |
6 ms |
3704 KB |
Output is correct |
4 |
Correct |
4 ms |
3452 KB |
Output is correct |
5 |
Correct |
6 ms |
3704 KB |
Output is correct |
6 |
Correct |
5 ms |
3676 KB |
Output is correct |
7 |
Correct |
4 ms |
3576 KB |
Output is correct |
8 |
Correct |
4 ms |
3448 KB |
Output is correct |
9 |
Correct |
6 ms |
3680 KB |
Output is correct |
10 |
Correct |
5 ms |
3676 KB |
Output is correct |
11 |
Correct |
6 ms |
3704 KB |
Output is correct |
12 |
Correct |
6 ms |
3752 KB |
Output is correct |
13 |
Correct |
6 ms |
3704 KB |
Output is correct |
14 |
Correct |
6 ms |
3704 KB |
Output is correct |
15 |
Correct |
6 ms |
3704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3548 KB |
Output is correct |
2 |
Correct |
6 ms |
3704 KB |
Output is correct |
3 |
Correct |
6 ms |
3704 KB |
Output is correct |
4 |
Correct |
4 ms |
3452 KB |
Output is correct |
5 |
Correct |
6 ms |
3704 KB |
Output is correct |
6 |
Correct |
5 ms |
3676 KB |
Output is correct |
7 |
Correct |
4 ms |
3576 KB |
Output is correct |
8 |
Correct |
4 ms |
3448 KB |
Output is correct |
9 |
Correct |
6 ms |
3680 KB |
Output is correct |
10 |
Correct |
5 ms |
3676 KB |
Output is correct |
11 |
Correct |
6 ms |
3704 KB |
Output is correct |
12 |
Correct |
6 ms |
3752 KB |
Output is correct |
13 |
Correct |
6 ms |
3704 KB |
Output is correct |
14 |
Correct |
6 ms |
3704 KB |
Output is correct |
15 |
Correct |
6 ms |
3704 KB |
Output is correct |
16 |
Correct |
296 ms |
23680 KB |
Output is correct |
17 |
Correct |
724 ms |
38580 KB |
Output is correct |
18 |
Correct |
48 ms |
7544 KB |
Output is correct |
19 |
Correct |
276 ms |
27856 KB |
Output is correct |
20 |
Correct |
748 ms |
38496 KB |
Output is correct |
21 |
Correct |
290 ms |
24560 KB |
Output is correct |
22 |
Correct |
233 ms |
26608 KB |
Output is correct |
23 |
Correct |
775 ms |
38272 KB |
Output is correct |
24 |
Correct |
821 ms |
38328 KB |
Output is correct |
25 |
Correct |
723 ms |
36732 KB |
Output is correct |
26 |
Correct |
291 ms |
27876 KB |
Output is correct |
27 |
Correct |
282 ms |
27908 KB |
Output is correct |
28 |
Correct |
278 ms |
27892 KB |
Output is correct |
29 |
Correct |
274 ms |
27884 KB |
Output is correct |
30 |
Correct |
277 ms |
27948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3448 KB |
Output is correct |
7 |
Correct |
4 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
4 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
218 ms |
18312 KB |
Output is correct |
2 |
Correct |
454 ms |
26056 KB |
Output is correct |
3 |
Correct |
448 ms |
25956 KB |
Output is correct |
4 |
Correct |
92 ms |
14792 KB |
Output is correct |
5 |
Correct |
438 ms |
26064 KB |
Output is correct |
6 |
Correct |
472 ms |
26204 KB |
Output is correct |
7 |
Correct |
455 ms |
25964 KB |
Output is correct |
8 |
Correct |
467 ms |
26156 KB |
Output is correct |
9 |
Correct |
471 ms |
26080 KB |
Output is correct |
10 |
Correct |
465 ms |
26064 KB |
Output is correct |
11 |
Correct |
489 ms |
26068 KB |
Output is correct |
12 |
Correct |
468 ms |
25980 KB |
Output is correct |
13 |
Correct |
453 ms |
26012 KB |
Output is correct |
14 |
Correct |
474 ms |
25984 KB |
Output is correct |
15 |
Correct |
484 ms |
26312 KB |
Output is correct |
16 |
Correct |
479 ms |
26052 KB |
Output is correct |
17 |
Correct |
518 ms |
26000 KB |
Output is correct |
18 |
Correct |
497 ms |
26048 KB |
Output is correct |
19 |
Correct |
106 ms |
14808 KB |
Output is correct |
20 |
Correct |
489 ms |
25972 KB |
Output is correct |
21 |
Correct |
442 ms |
26004 KB |
Output is correct |
22 |
Correct |
111 ms |
16744 KB |
Output is correct |
23 |
Correct |
105 ms |
15348 KB |
Output is correct |
24 |
Correct |
115 ms |
16748 KB |
Output is correct |
25 |
Correct |
113 ms |
16836 KB |
Output is correct |
26 |
Correct |
116 ms |
15440 KB |
Output is correct |
27 |
Correct |
118 ms |
14808 KB |
Output is correct |
28 |
Correct |
109 ms |
16748 KB |
Output is correct |
29 |
Correct |
96 ms |
14836 KB |
Output is correct |
30 |
Correct |
116 ms |
16824 KB |
Output is correct |
31 |
Correct |
98 ms |
14836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3548 KB |
Output is correct |
2 |
Correct |
6 ms |
3704 KB |
Output is correct |
3 |
Correct |
6 ms |
3704 KB |
Output is correct |
4 |
Correct |
4 ms |
3452 KB |
Output is correct |
5 |
Correct |
6 ms |
3704 KB |
Output is correct |
6 |
Correct |
5 ms |
3676 KB |
Output is correct |
7 |
Correct |
4 ms |
3576 KB |
Output is correct |
8 |
Correct |
4 ms |
3448 KB |
Output is correct |
9 |
Correct |
6 ms |
3680 KB |
Output is correct |
10 |
Correct |
5 ms |
3676 KB |
Output is correct |
11 |
Correct |
6 ms |
3704 KB |
Output is correct |
12 |
Correct |
6 ms |
3752 KB |
Output is correct |
13 |
Correct |
6 ms |
3704 KB |
Output is correct |
14 |
Correct |
6 ms |
3704 KB |
Output is correct |
15 |
Correct |
6 ms |
3704 KB |
Output is correct |
16 |
Correct |
296 ms |
23680 KB |
Output is correct |
17 |
Correct |
724 ms |
38580 KB |
Output is correct |
18 |
Correct |
48 ms |
7544 KB |
Output is correct |
19 |
Correct |
276 ms |
27856 KB |
Output is correct |
20 |
Correct |
748 ms |
38496 KB |
Output is correct |
21 |
Correct |
290 ms |
24560 KB |
Output is correct |
22 |
Correct |
233 ms |
26608 KB |
Output is correct |
23 |
Correct |
775 ms |
38272 KB |
Output is correct |
24 |
Correct |
821 ms |
38328 KB |
Output is correct |
25 |
Correct |
723 ms |
36732 KB |
Output is correct |
26 |
Correct |
291 ms |
27876 KB |
Output is correct |
27 |
Correct |
282 ms |
27908 KB |
Output is correct |
28 |
Correct |
278 ms |
27892 KB |
Output is correct |
29 |
Correct |
274 ms |
27884 KB |
Output is correct |
30 |
Correct |
277 ms |
27948 KB |
Output is correct |
31 |
Correct |
5 ms |
3448 KB |
Output is correct |
32 |
Correct |
5 ms |
3448 KB |
Output is correct |
33 |
Correct |
5 ms |
3448 KB |
Output is correct |
34 |
Correct |
5 ms |
3448 KB |
Output is correct |
35 |
Correct |
5 ms |
3448 KB |
Output is correct |
36 |
Correct |
5 ms |
3448 KB |
Output is correct |
37 |
Correct |
4 ms |
3448 KB |
Output is correct |
38 |
Correct |
5 ms |
3448 KB |
Output is correct |
39 |
Correct |
5 ms |
3448 KB |
Output is correct |
40 |
Correct |
4 ms |
3448 KB |
Output is correct |
41 |
Correct |
218 ms |
18312 KB |
Output is correct |
42 |
Correct |
454 ms |
26056 KB |
Output is correct |
43 |
Correct |
448 ms |
25956 KB |
Output is correct |
44 |
Correct |
92 ms |
14792 KB |
Output is correct |
45 |
Correct |
438 ms |
26064 KB |
Output is correct |
46 |
Correct |
472 ms |
26204 KB |
Output is correct |
47 |
Correct |
455 ms |
25964 KB |
Output is correct |
48 |
Correct |
467 ms |
26156 KB |
Output is correct |
49 |
Correct |
471 ms |
26080 KB |
Output is correct |
50 |
Correct |
465 ms |
26064 KB |
Output is correct |
51 |
Correct |
489 ms |
26068 KB |
Output is correct |
52 |
Correct |
468 ms |
25980 KB |
Output is correct |
53 |
Correct |
453 ms |
26012 KB |
Output is correct |
54 |
Correct |
474 ms |
25984 KB |
Output is correct |
55 |
Correct |
484 ms |
26312 KB |
Output is correct |
56 |
Correct |
479 ms |
26052 KB |
Output is correct |
57 |
Correct |
518 ms |
26000 KB |
Output is correct |
58 |
Correct |
497 ms |
26048 KB |
Output is correct |
59 |
Correct |
106 ms |
14808 KB |
Output is correct |
60 |
Correct |
489 ms |
25972 KB |
Output is correct |
61 |
Correct |
442 ms |
26004 KB |
Output is correct |
62 |
Correct |
111 ms |
16744 KB |
Output is correct |
63 |
Correct |
105 ms |
15348 KB |
Output is correct |
64 |
Correct |
115 ms |
16748 KB |
Output is correct |
65 |
Correct |
113 ms |
16836 KB |
Output is correct |
66 |
Correct |
116 ms |
15440 KB |
Output is correct |
67 |
Correct |
118 ms |
14808 KB |
Output is correct |
68 |
Correct |
109 ms |
16748 KB |
Output is correct |
69 |
Correct |
96 ms |
14836 KB |
Output is correct |
70 |
Correct |
116 ms |
16824 KB |
Output is correct |
71 |
Correct |
98 ms |
14836 KB |
Output is correct |
72 |
Correct |
512 ms |
31116 KB |
Output is correct |
73 |
Correct |
796 ms |
38488 KB |
Output is correct |
74 |
Correct |
785 ms |
38408 KB |
Output is correct |
75 |
Correct |
780 ms |
38420 KB |
Output is correct |
76 |
Correct |
806 ms |
38532 KB |
Output is correct |
77 |
Correct |
727 ms |
38752 KB |
Output is correct |
78 |
Correct |
797 ms |
38548 KB |
Output is correct |
79 |
Correct |
803 ms |
38812 KB |
Output is correct |
80 |
Correct |
789 ms |
38728 KB |
Output is correct |
81 |
Correct |
790 ms |
38812 KB |
Output is correct |
82 |
Correct |
796 ms |
38752 KB |
Output is correct |
83 |
Correct |
795 ms |
38776 KB |
Output is correct |
84 |
Correct |
787 ms |
38288 KB |
Output is correct |
85 |
Correct |
687 ms |
35676 KB |
Output is correct |
86 |
Correct |
769 ms |
35316 KB |
Output is correct |
87 |
Correct |
755 ms |
35540 KB |
Output is correct |
88 |
Correct |
780 ms |
35528 KB |
Output is correct |
89 |
Correct |
404 ms |
25324 KB |
Output is correct |
90 |
Correct |
755 ms |
35536 KB |
Output is correct |
91 |
Correct |
483 ms |
26596 KB |
Output is correct |
92 |
Correct |
355 ms |
26600 KB |
Output is correct |
93 |
Correct |
469 ms |
25952 KB |
Output is correct |
94 |
Correct |
351 ms |
26348 KB |
Output is correct |
95 |
Correct |
377 ms |
26600 KB |
Output is correct |
96 |
Correct |
608 ms |
25208 KB |
Output is correct |
97 |
Correct |
427 ms |
24920 KB |
Output is correct |
98 |
Correct |
371 ms |
26344 KB |
Output is correct |
99 |
Correct |
390 ms |
24920 KB |
Output is correct |
100 |
Correct |
384 ms |
26524 KB |
Output is correct |