#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,dp[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];
// cout << p[i] << " ";
}
// cout << endl;
}
void dfs(ll x){
//cout << x << " " << rev[x].size() << endl;
dp[x] = 100000000000000;
for(int i=0; i<rev[x].size(); i++)
dp[x] = min(dp[x] , dp[rev[x][i]]);
dp[x] = min(dp[x] , du[x]);
ans = min(ans , dp[x] + df[x]);
//cout << dp[x] << " " << df[x] << "\n\n";
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);
//cout << i << "<-->" << v[i][j].f << endl;
}
for(int i=1; i<=n; i++)
raod[i] = (ll)rev[i].size();
ans = du[f];
// cout << du[f] << " " << f << " " << u << endl;
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:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<rev[x].size(); i++)
~^~~~~~~~~~~~~~
commuter_pass.cpp:44: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:72: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 |
688 ms |
35768 KB |
Output is correct |
2 |
Correct |
618 ms |
35120 KB |
Output is correct |
3 |
Correct |
587 ms |
39616 KB |
Output is correct |
4 |
Correct |
553 ms |
35504 KB |
Output is correct |
5 |
Correct |
507 ms |
36572 KB |
Output is correct |
6 |
Correct |
670 ms |
35768 KB |
Output is correct |
7 |
Correct |
610 ms |
37084 KB |
Output is correct |
8 |
Correct |
650 ms |
36652 KB |
Output is correct |
9 |
Correct |
661 ms |
35164 KB |
Output is correct |
10 |
Correct |
490 ms |
35600 KB |
Output is correct |
11 |
Correct |
230 ms |
30816 KB |
Output is correct |
12 |
Correct |
684 ms |
34980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
652 ms |
36020 KB |
Output is correct |
2 |
Correct |
863 ms |
36288 KB |
Output is correct |
3 |
Correct |
782 ms |
35668 KB |
Output is correct |
4 |
Incorrect |
779 ms |
36008 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
29 ms |
16376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
688 ms |
35768 KB |
Output is correct |
2 |
Correct |
618 ms |
35120 KB |
Output is correct |
3 |
Correct |
587 ms |
39616 KB |
Output is correct |
4 |
Correct |
553 ms |
35504 KB |
Output is correct |
5 |
Correct |
507 ms |
36572 KB |
Output is correct |
6 |
Correct |
670 ms |
35768 KB |
Output is correct |
7 |
Correct |
610 ms |
37084 KB |
Output is correct |
8 |
Correct |
650 ms |
36652 KB |
Output is correct |
9 |
Correct |
661 ms |
35164 KB |
Output is correct |
10 |
Correct |
490 ms |
35600 KB |
Output is correct |
11 |
Correct |
230 ms |
30816 KB |
Output is correct |
12 |
Correct |
684 ms |
34980 KB |
Output is correct |
13 |
Correct |
652 ms |
36020 KB |
Output is correct |
14 |
Correct |
863 ms |
36288 KB |
Output is correct |
15 |
Correct |
782 ms |
35668 KB |
Output is correct |
16 |
Incorrect |
779 ms |
36008 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |