#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define N 200005
#define mp make_pair
using namespace std;
ll ds[N],dt[N],du[N],df[N],raod[N],s,t,u,f,n,m,dp1[N],dp2[N],p[N],ans=100000000000000;
vector<pair<ll,ll> >v[N];
vector<ll>g[N],rev[N];
void dj(ll k){
vector<ll> d (n + 1, 100000000000000);
d[k] = 0;
set < pair<ll,ll> > q;
q.insert (make_pair (d[k], k));
while(!q.empty()) {
ll x = q.begin()->s;
q.erase (q.begin());
for (int i=0; i<v[x].size(); i++) {
ll to = v[x][i].f,
len = v[x][i].s;
if (d[x] + len < d[to]) {
if(q.find(mp(d[to] , to)) != q.end())q.erase(make_pair (d[to], to));
d[to] = d[x] + len;
q.insert(make_pair (d[to], to));
}
}
}
for(int i=1; i<=n; i++){
p[i] = d[i];
}
}
void dfs(ll x){
dp1[x] = 100000000000000;
dp2[x] = 100000000000000;
for(int i=0; i<rev[x].size(); i++)
dp1[x] = min(dp1[x] , dp1[rev[x][i]]);
dp1[x] = min(dp1[x] , du[x]);
ans = min(ans , dp1[x] + df[x]);
for(int i=0; i<rev[x].size(); i++)
dp2[x] = min(dp2[x] , dp2[rev[x][i]]);
dp2[x] = min(dp2[x] , df[x]);
ans = min(ans , dp2[x] + du[x]);
for(int i=0; i<g[x].size(); i++)
if(raod[g[x][i]] <= 1)dfs(g[x][i]);
else raod[g[x][i]]--;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m >> s >> t >> u >> f;
for(int i=1; i<=m; i++){
int x,y,z;
cin >> x >> y >> z;
v[x].pb(mp(y , z));
v[y].pb(mp(x , z));
}
dj(s);
for(int i=1; i<=n; i++)
ds[i] = p[i];
dj(t);
for(int i=1; i<=n; i++)
dt[i] = p[i];
dj(u);
for(int i=1; i<=n; i++)
du[i] = p[i];
dj(f);
for(int i=1; i<=n; i++)
df[i] = p[i];
for(int i=1; i<=n; i++)
for(int j=0; j<v[i].size(); j++)
if(ds[i] + v[i][j].s + dt[v[i][j].f] == ds[t]){
g[i].pb(v[i][j].f),
rev[v[i][j].f].pb(i);
}
for(int i=1; i<=n; i++)
raod[i] = (ll)rev[i].size();
ans = du[f];
dfs(s);
cout << ans << endl;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dj(long long int)':
commuter_pass.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<rev[x].size(); i++)
~^~~~~~~~~~~~~~
commuter_pass.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<rev[x].size(); i++)
~^~~~~~~~~~~~~~
commuter_pass.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[x].size(); i++)
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<v[i].size(); j++)
~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
809 ms |
31676 KB |
Output is correct |
2 |
Correct |
649 ms |
32508 KB |
Output is correct |
3 |
Correct |
597 ms |
36692 KB |
Output is correct |
4 |
Correct |
608 ms |
31836 KB |
Output is correct |
5 |
Correct |
586 ms |
33696 KB |
Output is correct |
6 |
Correct |
719 ms |
31796 KB |
Output is correct |
7 |
Correct |
619 ms |
34336 KB |
Output is correct |
8 |
Correct |
613 ms |
34076 KB |
Output is correct |
9 |
Correct |
590 ms |
30704 KB |
Output is correct |
10 |
Correct |
432 ms |
31108 KB |
Output is correct |
11 |
Correct |
169 ms |
29656 KB |
Output is correct |
12 |
Correct |
612 ms |
30776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
771 ms |
33100 KB |
Output is correct |
2 |
Correct |
686 ms |
33480 KB |
Output is correct |
3 |
Correct |
679 ms |
32804 KB |
Output is correct |
4 |
Correct |
666 ms |
33400 KB |
Output is correct |
5 |
Correct |
692 ms |
37476 KB |
Output is correct |
6 |
Correct |
592 ms |
39708 KB |
Output is correct |
7 |
Correct |
692 ms |
40340 KB |
Output is correct |
8 |
Correct |
655 ms |
36984 KB |
Output is correct |
9 |
Correct |
677 ms |
37388 KB |
Output is correct |
10 |
Correct |
677 ms |
36400 KB |
Output is correct |
11 |
Correct |
198 ms |
33628 KB |
Output is correct |
12 |
Correct |
588 ms |
40180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
15992 KB |
Output is correct |
2 |
Correct |
15 ms |
14584 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
35 ms |
17912 KB |
Output is correct |
5 |
Correct |
25 ms |
16248 KB |
Output is correct |
6 |
Correct |
15 ms |
14584 KB |
Output is correct |
7 |
Correct |
16 ms |
14712 KB |
Output is correct |
8 |
Correct |
17 ms |
14712 KB |
Output is correct |
9 |
Correct |
15 ms |
14584 KB |
Output is correct |
10 |
Correct |
25 ms |
16248 KB |
Output is correct |
11 |
Correct |
15 ms |
14584 KB |
Output is correct |
12 |
Correct |
15 ms |
14588 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
15 ms |
14584 KB |
Output is correct |
15 |
Correct |
16 ms |
14584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
809 ms |
31676 KB |
Output is correct |
2 |
Correct |
649 ms |
32508 KB |
Output is correct |
3 |
Correct |
597 ms |
36692 KB |
Output is correct |
4 |
Correct |
608 ms |
31836 KB |
Output is correct |
5 |
Correct |
586 ms |
33696 KB |
Output is correct |
6 |
Correct |
719 ms |
31796 KB |
Output is correct |
7 |
Correct |
619 ms |
34336 KB |
Output is correct |
8 |
Correct |
613 ms |
34076 KB |
Output is correct |
9 |
Correct |
590 ms |
30704 KB |
Output is correct |
10 |
Correct |
432 ms |
31108 KB |
Output is correct |
11 |
Correct |
169 ms |
29656 KB |
Output is correct |
12 |
Correct |
612 ms |
30776 KB |
Output is correct |
13 |
Correct |
771 ms |
33100 KB |
Output is correct |
14 |
Correct |
686 ms |
33480 KB |
Output is correct |
15 |
Correct |
679 ms |
32804 KB |
Output is correct |
16 |
Correct |
666 ms |
33400 KB |
Output is correct |
17 |
Correct |
692 ms |
37476 KB |
Output is correct |
18 |
Correct |
592 ms |
39708 KB |
Output is correct |
19 |
Correct |
692 ms |
40340 KB |
Output is correct |
20 |
Correct |
655 ms |
36984 KB |
Output is correct |
21 |
Correct |
677 ms |
37388 KB |
Output is correct |
22 |
Correct |
677 ms |
36400 KB |
Output is correct |
23 |
Correct |
198 ms |
33628 KB |
Output is correct |
24 |
Correct |
588 ms |
40180 KB |
Output is correct |
25 |
Correct |
26 ms |
15992 KB |
Output is correct |
26 |
Correct |
15 ms |
14584 KB |
Output is correct |
27 |
Correct |
15 ms |
14456 KB |
Output is correct |
28 |
Correct |
35 ms |
17912 KB |
Output is correct |
29 |
Correct |
25 ms |
16248 KB |
Output is correct |
30 |
Correct |
15 ms |
14584 KB |
Output is correct |
31 |
Correct |
16 ms |
14712 KB |
Output is correct |
32 |
Correct |
17 ms |
14712 KB |
Output is correct |
33 |
Correct |
15 ms |
14584 KB |
Output is correct |
34 |
Correct |
25 ms |
16248 KB |
Output is correct |
35 |
Correct |
15 ms |
14584 KB |
Output is correct |
36 |
Correct |
15 ms |
14588 KB |
Output is correct |
37 |
Correct |
15 ms |
14584 KB |
Output is correct |
38 |
Correct |
15 ms |
14584 KB |
Output is correct |
39 |
Correct |
16 ms |
14584 KB |
Output is correct |
40 |
Correct |
656 ms |
38128 KB |
Output is correct |
41 |
Correct |
606 ms |
35244 KB |
Output is correct |
42 |
Correct |
589 ms |
35224 KB |
Output is correct |
43 |
Correct |
194 ms |
35676 KB |
Output is correct |
44 |
Correct |
206 ms |
35644 KB |
Output is correct |
45 |
Correct |
518 ms |
41416 KB |
Output is correct |
46 |
Correct |
505 ms |
40932 KB |
Output is correct |
47 |
Correct |
688 ms |
35460 KB |
Output is correct |
48 |
Correct |
202 ms |
34012 KB |
Output is correct |
49 |
Correct |
459 ms |
37820 KB |
Output is correct |
50 |
Correct |
525 ms |
39512 KB |
Output is correct |
51 |
Correct |
513 ms |
41260 KB |
Output is correct |