#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
struct edge { int u,v,w; };
vector<edge> edges;
LLI dist[6000][6000];
pair<LLI,int> best[6000][2001][2];
int X[100000];
int main() {
int i;
int N,M,T,L;
int A,B,C,P,Q;
scanf("%d %d %d %d",&N,&M,&T,&L);
for (i = 0; i < M; i++) {
scanf("%d %d %d",&A,&B,&C);
A--,B--;
edges.pb((edge){A,B,C});
edges.pb((edge){B,A,C});
}
for (i = 0; i < L; i++) scanf("%d",&X[i]),X[i]--;
int j,k;
for (i = 0; i < N; i++) edges.pb((edge){N,i,0});
for (i = 0; i < edges.size(); i++) fill(dist[i],dist[i]+edges.size(),1e18),dist[i][i] = 0;
for (i = 0; i < edges.size(); i++) {
for (j = 0; j < edges.size(); j++) {
if ((edges[i].v == edges[j].u) && (edges[i].u != edges[j].v)) dist[i][j] = edges[j].w;
}
}
for (k = 0; k < edges.size(); k++) {
for (i = 0; i < edges.size(); i++) {
for (j = 0; j < edges.size(); j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
//for(i=0;i<2*M;i++){
// for(j=0;j<2*M;j++)cout<<dist[i][j]<<" ";
// cout<<endl;
//}
for (i = 0; i < edges.size(); i++) {
for (j = 0; j < N+1; j++) best[i][j][0] = best[i][j][1] = mp(1e18,-1);
for (j = 0; j < edges.size(); j++) {
pair<LLI,int> p = mp(dist[i][j],j);
if (p.first <= best[i][edges[j].v][0].first)
best[i][edges[j].v][1] = best[i][edges[j].v][0],best[i][edges[j].v][0] = p;
else if (p.first <= best[i][edges[j].v][1].first) best[i][edges[j].v][1] = p;
}
}
for (i = 0; i < T; i++) {
scanf("%d %d",&P,&Q);
P--,Q--;
X[P] = Q;
int u = X[0];
LLI d1 = 0,d2 = 0;
int e1 = u+2*M,e2 = u+2*M;
for (j = 1; j < L; j++) {
LLI nd1 = 1e18,nd2 = 1e18;
int ne1 = -1,ne2 = -1;
vector<pair<LLI,int> > b;
for (k = 0; k < 2; k++) {
if (e1 != -1) b.pb(mp(best[e1][X[j]][k].first+d1,best[e1][X[j]][k].second));
if (e2 != -1) b.pb(mp(best[e2][X[j]][k].first+d2,best[e2][X[j]][k].second));
/*if ((e1 != -1) && (best[e1][X[j]][k].first+d1 <= nd1))
nd2 = nd1,ne2 = ne1,nd1 = best[e1][X[j]][k].first+d1,ne1 = best[e1][X[j]][k].second;
else if ((e1 != -1) && (best[e1][X[j]][k].first+d1 <= nd2))
nd2 = best[e1][X[j]][k].first+d1,ne2 = best[e1][X[j]][k].second;
if ((e2 != -1) && (best[e2][X[j]][k].first+d2 <= nd1))
nd2 = nd1,ne2 = ne1,nd1 = best[e2][X[j]][k].first+d2,ne1 = best[e2][X[j]][k].second;
else if ((e2 != -1) && (best[e2][X[j]][k].first+d2 <= nd2))
nd2 = best[e2][X[j]][k].first+d2,ne2 = best[e2][X[j]][k].second;*/
}
while (b.size() < 4) b.pb(mp(1e18,-1));
sort(b.begin(),b.end());
if (b[1].second == b[0].second) {
if (b[2].second == b[0].second) {
if (b[3].second != b[0].second) b[1] = b[3];
}
else b[1] = b[2];
}
nd1 = min(b[0].first,(LLI) 1e18),ne1 = b[0].second;
nd2 = min(b[1].first,(LLI) 1e18),ne2 = b[1].second;
d1 = nd1,e1 = ne1,d2 = nd2,e2 = ne2;
}
printf("%lld\n",(d1 > 1e17) ? -1:d1);
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) fill(dist[i],dist[i]+edges.size(),1e18),dist[i][i] = 0;
~~^~~~~~~~~~~~~~
wild_boar.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edges.size(); j++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (k = 0; k < edges.size(); k++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edges.size(); j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
~~^~~~~~~~~~~~~~
wild_boar.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edges.size(); j++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&N,&M,&T,&L);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&A,&B,&C);
~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:26:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < L; i++) scanf("%d",&X[i]),X[i]--;
~~~~~~~~~~~~~~~~~^~~~~~~
wild_boar.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&P,&Q);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
632 KB |
Output is correct |
20 |
Correct |
2 ms |
632 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
2 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
632 KB |
Output is correct |
20 |
Correct |
2 ms |
632 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
2 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
4 ms |
1276 KB |
Output is correct |
27 |
Correct |
68 ms |
5132 KB |
Output is correct |
28 |
Correct |
70 ms |
5132 KB |
Output is correct |
29 |
Correct |
457 ms |
12664 KB |
Output is correct |
30 |
Correct |
452 ms |
12636 KB |
Output is correct |
31 |
Correct |
450 ms |
12664 KB |
Output is correct |
32 |
Correct |
447 ms |
12664 KB |
Output is correct |
33 |
Correct |
560 ms |
15352 KB |
Output is correct |
34 |
Correct |
555 ms |
15224 KB |
Output is correct |
35 |
Correct |
549 ms |
15096 KB |
Output is correct |
36 |
Correct |
543 ms |
14988 KB |
Output is correct |
37 |
Correct |
557 ms |
15224 KB |
Output is correct |
38 |
Correct |
665 ms |
17588 KB |
Output is correct |
39 |
Correct |
660 ms |
17528 KB |
Output is correct |
40 |
Correct |
664 ms |
17656 KB |
Output is correct |
41 |
Correct |
687 ms |
17656 KB |
Output is correct |
42 |
Correct |
729 ms |
19128 KB |
Output is correct |
43 |
Correct |
812 ms |
20472 KB |
Output is correct |
44 |
Correct |
793 ms |
20472 KB |
Output is correct |
45 |
Correct |
931 ms |
23288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
632 KB |
Output is correct |
20 |
Correct |
2 ms |
632 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
2 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
4 ms |
1276 KB |
Output is correct |
27 |
Correct |
68 ms |
5132 KB |
Output is correct |
28 |
Correct |
70 ms |
5132 KB |
Output is correct |
29 |
Correct |
457 ms |
12664 KB |
Output is correct |
30 |
Correct |
452 ms |
12636 KB |
Output is correct |
31 |
Correct |
450 ms |
12664 KB |
Output is correct |
32 |
Correct |
447 ms |
12664 KB |
Output is correct |
33 |
Correct |
560 ms |
15352 KB |
Output is correct |
34 |
Correct |
555 ms |
15224 KB |
Output is correct |
35 |
Correct |
549 ms |
15096 KB |
Output is correct |
36 |
Correct |
543 ms |
14988 KB |
Output is correct |
37 |
Correct |
557 ms |
15224 KB |
Output is correct |
38 |
Correct |
665 ms |
17588 KB |
Output is correct |
39 |
Correct |
660 ms |
17528 KB |
Output is correct |
40 |
Correct |
664 ms |
17656 KB |
Output is correct |
41 |
Correct |
687 ms |
17656 KB |
Output is correct |
42 |
Correct |
729 ms |
19128 KB |
Output is correct |
43 |
Correct |
812 ms |
20472 KB |
Output is correct |
44 |
Correct |
793 ms |
20472 KB |
Output is correct |
45 |
Correct |
931 ms |
23288 KB |
Output is correct |
46 |
Correct |
2174 ms |
28996 KB |
Output is correct |
47 |
Execution timed out |
18108 ms |
177652 KB |
Time limit exceeded |
48 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
632 KB |
Output is correct |
20 |
Correct |
2 ms |
632 KB |
Output is correct |
21 |
Correct |
2 ms |
504 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
2 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
4 ms |
1276 KB |
Output is correct |
27 |
Correct |
68 ms |
5132 KB |
Output is correct |
28 |
Correct |
70 ms |
5132 KB |
Output is correct |
29 |
Correct |
457 ms |
12664 KB |
Output is correct |
30 |
Correct |
452 ms |
12636 KB |
Output is correct |
31 |
Correct |
450 ms |
12664 KB |
Output is correct |
32 |
Correct |
447 ms |
12664 KB |
Output is correct |
33 |
Correct |
560 ms |
15352 KB |
Output is correct |
34 |
Correct |
555 ms |
15224 KB |
Output is correct |
35 |
Correct |
549 ms |
15096 KB |
Output is correct |
36 |
Correct |
543 ms |
14988 KB |
Output is correct |
37 |
Correct |
557 ms |
15224 KB |
Output is correct |
38 |
Correct |
665 ms |
17588 KB |
Output is correct |
39 |
Correct |
660 ms |
17528 KB |
Output is correct |
40 |
Correct |
664 ms |
17656 KB |
Output is correct |
41 |
Correct |
687 ms |
17656 KB |
Output is correct |
42 |
Correct |
729 ms |
19128 KB |
Output is correct |
43 |
Correct |
812 ms |
20472 KB |
Output is correct |
44 |
Correct |
793 ms |
20472 KB |
Output is correct |
45 |
Correct |
931 ms |
23288 KB |
Output is correct |
46 |
Correct |
2174 ms |
28996 KB |
Output is correct |
47 |
Execution timed out |
18108 ms |
177652 KB |
Time limit exceeded |
48 |
Halted |
0 ms |
0 KB |
- |