#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001;
const int64_t INF = 1e18;
vector<pair<int,int>> g[maxn];
vector<int> g2[maxn];
vector<int> g3[maxn];
vector<int> ts;
int64_t dp[maxn];
int64_t d[maxn],ds[maxn],dt[maxn],du[maxn],dv[maxn];
int vis[maxn];
set<pair<int64_t,int>> ff;
int n;
void dij(int s)
{
for(int j = 0;j < n;++j)
{
d[j] = INF;
vis[j] = 0;
}
d[s] = 0;
ff.insert({0,s});
while(ff.size())
{
int v = (*ff.begin()).second;
ff.erase(ff.begin());
vis[v] = 1;
for(auto [u,dd]:g[v])
{
if(d[u] > d[v] + dd && !vis[u])
{
ff.erase({d[u],u});
d[u] = d[v] + dd;
ff.insert({d[u],u});
}
}
}
return ;
}
void dfs(int v)
{
vis[v] = 1;
for(auto u:g2[v])
{
if(!vis[u])
{
dfs(u);
}
}
ts.push_back(v);
return ;
}
void dfs2(int v)
{
vis[v] = 1;
for(auto u:g3[v])
{
if(!vis[u])
{
dfs2(u);
}
}
ts.push_back(v);
return ;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> n >> m;
int s,t,u,v;
cin >> s >> t >> u >> v;
s--;
t--;
u--;
v--;
for(int i = 0;i < m;++i)
{
int a,b,c;
cin >> a >> b >> c;
a--;
b--;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
dij(s);
for(int j = 0;j < n;++j)
{
ds[j] = d[j];
}
dij(t);
for(int j = 0;j < n;++j)
{
dt[j] = d[j];
}
dij(u);
for(int j = 0;j < n;++j)
{
du[j] = d[j];
}
dij(v);
for(int j = 0;j < n;++j)
{
dv[j] = d[j];
}
for(int v = 0;v < n;++v)
{
for(auto [u,d] : g[v])
{
if(ds[u]-ds[v] == d && dt[v]-dt[u] == d && ds[u] + dt[u] == ds[t])
{
g2[v].push_back(u);
g3[u].push_back(v);
}
}
}
for(int i = 0;i < n;++i)
vis[i] = 0;
dfs(s);
int64_t ans = du[v];
for(int i = 0;i < ts.size();++i)
{
dp[ts[i]] = dv[ts[i]];
for(auto u : g2[ts[i]])
{
dp[ts[i]] = min(dp[ts[i]],dp[u]);
}
ans = min(ans,dp[ts[i]]+du[ts[i]]);
}
for(int i = 0;i < n;++i)
vis[i] = 0;
ts.clear();
dfs2(t);
for(int i = 0;i < ts.size();++i)
{
dp[ts[i]] = dv[ts[i]];
for(auto u : g3[ts[i]])
{
dp[ts[i]] = min(dp[ts[i]],dp[u]);
}
ans = min(ans,dp[ts[i]]+du[ts[i]]);
}
cout << ans << "\n";
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0;i < ts.size();++i)
| ~~^~~~~~~~~~~
commuter_pass.cpp:140:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i = 0;i < ts.size();++i)
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
373 ms |
25672 KB |
Output is correct |
2 |
Correct |
269 ms |
24500 KB |
Output is correct |
3 |
Correct |
343 ms |
30188 KB |
Output is correct |
4 |
Correct |
326 ms |
25680 KB |
Output is correct |
5 |
Correct |
266 ms |
25516 KB |
Output is correct |
6 |
Correct |
313 ms |
25680 KB |
Output is correct |
7 |
Correct |
352 ms |
26196 KB |
Output is correct |
8 |
Correct |
286 ms |
25616 KB |
Output is correct |
9 |
Correct |
297 ms |
25172 KB |
Output is correct |
10 |
Correct |
194 ms |
25624 KB |
Output is correct |
11 |
Correct |
78 ms |
22576 KB |
Output is correct |
12 |
Correct |
300 ms |
24828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
299 ms |
26556 KB |
Output is correct |
2 |
Correct |
311 ms |
25684 KB |
Output is correct |
3 |
Correct |
324 ms |
25404 KB |
Output is correct |
4 |
Correct |
386 ms |
25428 KB |
Output is correct |
5 |
Correct |
326 ms |
26224 KB |
Output is correct |
6 |
Correct |
268 ms |
28884 KB |
Output is correct |
7 |
Correct |
324 ms |
29860 KB |
Output is correct |
8 |
Correct |
307 ms |
25680 KB |
Output is correct |
9 |
Correct |
296 ms |
26196 KB |
Output is correct |
10 |
Correct |
310 ms |
25412 KB |
Output is correct |
11 |
Correct |
111 ms |
25008 KB |
Output is correct |
12 |
Correct |
283 ms |
29304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
13400 KB |
Output is correct |
2 |
Correct |
3 ms |
12380 KB |
Output is correct |
3 |
Correct |
3 ms |
12380 KB |
Output is correct |
4 |
Correct |
15 ms |
14476 KB |
Output is correct |
5 |
Correct |
7 ms |
13404 KB |
Output is correct |
6 |
Correct |
3 ms |
12380 KB |
Output is correct |
7 |
Correct |
4 ms |
12380 KB |
Output is correct |
8 |
Correct |
4 ms |
12380 KB |
Output is correct |
9 |
Correct |
4 ms |
12380 KB |
Output is correct |
10 |
Correct |
9 ms |
13404 KB |
Output is correct |
11 |
Correct |
3 ms |
12380 KB |
Output is correct |
12 |
Correct |
3 ms |
12380 KB |
Output is correct |
13 |
Correct |
3 ms |
12376 KB |
Output is correct |
14 |
Correct |
4 ms |
12380 KB |
Output is correct |
15 |
Correct |
3 ms |
12380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
373 ms |
25672 KB |
Output is correct |
2 |
Correct |
269 ms |
24500 KB |
Output is correct |
3 |
Correct |
343 ms |
30188 KB |
Output is correct |
4 |
Correct |
326 ms |
25680 KB |
Output is correct |
5 |
Correct |
266 ms |
25516 KB |
Output is correct |
6 |
Correct |
313 ms |
25680 KB |
Output is correct |
7 |
Correct |
352 ms |
26196 KB |
Output is correct |
8 |
Correct |
286 ms |
25616 KB |
Output is correct |
9 |
Correct |
297 ms |
25172 KB |
Output is correct |
10 |
Correct |
194 ms |
25624 KB |
Output is correct |
11 |
Correct |
78 ms |
22576 KB |
Output is correct |
12 |
Correct |
300 ms |
24828 KB |
Output is correct |
13 |
Correct |
299 ms |
26556 KB |
Output is correct |
14 |
Correct |
311 ms |
25684 KB |
Output is correct |
15 |
Correct |
324 ms |
25404 KB |
Output is correct |
16 |
Correct |
386 ms |
25428 KB |
Output is correct |
17 |
Correct |
326 ms |
26224 KB |
Output is correct |
18 |
Correct |
268 ms |
28884 KB |
Output is correct |
19 |
Correct |
324 ms |
29860 KB |
Output is correct |
20 |
Correct |
307 ms |
25680 KB |
Output is correct |
21 |
Correct |
296 ms |
26196 KB |
Output is correct |
22 |
Correct |
310 ms |
25412 KB |
Output is correct |
23 |
Correct |
111 ms |
25008 KB |
Output is correct |
24 |
Correct |
283 ms |
29304 KB |
Output is correct |
25 |
Correct |
8 ms |
13400 KB |
Output is correct |
26 |
Correct |
3 ms |
12380 KB |
Output is correct |
27 |
Correct |
3 ms |
12380 KB |
Output is correct |
28 |
Correct |
15 ms |
14476 KB |
Output is correct |
29 |
Correct |
7 ms |
13404 KB |
Output is correct |
30 |
Correct |
3 ms |
12380 KB |
Output is correct |
31 |
Correct |
4 ms |
12380 KB |
Output is correct |
32 |
Correct |
4 ms |
12380 KB |
Output is correct |
33 |
Correct |
4 ms |
12380 KB |
Output is correct |
34 |
Correct |
9 ms |
13404 KB |
Output is correct |
35 |
Correct |
3 ms |
12380 KB |
Output is correct |
36 |
Correct |
3 ms |
12380 KB |
Output is correct |
37 |
Correct |
3 ms |
12376 KB |
Output is correct |
38 |
Correct |
4 ms |
12380 KB |
Output is correct |
39 |
Correct |
3 ms |
12380 KB |
Output is correct |
40 |
Correct |
316 ms |
28804 KB |
Output is correct |
41 |
Correct |
294 ms |
25548 KB |
Output is correct |
42 |
Correct |
326 ms |
25356 KB |
Output is correct |
43 |
Correct |
99 ms |
26836 KB |
Output is correct |
44 |
Correct |
123 ms |
26832 KB |
Output is correct |
45 |
Correct |
274 ms |
28624 KB |
Output is correct |
46 |
Correct |
233 ms |
28364 KB |
Output is correct |
47 |
Correct |
361 ms |
25684 KB |
Output is correct |
48 |
Correct |
119 ms |
24792 KB |
Output is correct |
49 |
Correct |
227 ms |
28360 KB |
Output is correct |
50 |
Correct |
239 ms |
27316 KB |
Output is correct |
51 |
Correct |
215 ms |
28584 KB |
Output is correct |