#include <bits/stdc++.h>
using namespace std;
long long dist[3][100005], dp[3][100005], deg[100005], n, m, a, b, c, d, ans=1e18;
vector<pair<long long, long long> > adj[100005];
priority_queue<pair<long long, long long> > pq;
vector<long long> back[100005], front[100005];
bool visited[100005];
queue<long long> q;
void dijkstra(long long start)
{
for (long long i=1; i<=n; i++)
{
visited[i]=0;
dist[start][i]=1e18;
}
if (start==0)
{
dist[start][a]=0;
pq.push({0, a});
}
else if (start==1)
{
dist[start][c]=0;
pq.push({0, c});
}
else
{
dist[start][d]=0;
pq.push({0, d});
}
while (!pq.empty())
{
long long u=pq.top().second;
pq.pop();
if (visited[u])
continue;
visited[u]=1;
for (long long i=0; i<adj[u].size(); i++)
{
long long v=adj[u][i].first, w=adj[u][i].second;
if (dist[start][u]+w<dist[start][v])
{
dist[start][v]=dist[start][u]+w;
pq.push({-dist[start][v], v});
if (!start)
{
back[v].clear();
back[v].push_back(u);
}
}
else if (!start && dist[start][u]+w==dist[start][v])
back[v].push_back(u);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> a >> b >> c >> d;
for (long long i=1; i<=m; i++)
{
long long u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dijkstra(0);
dijkstra(1);
dijkstra(2);
for (long long i=1; i<=n; i++)
{
// cout << "dist of " << i << ": " << dist[0][i] << ' ' << dist[1][i] << ' ' << dist[2][i] << '\n';
deg[i]=back[i].size();
for (long long j=0; j<deg[i]; j++)
// {
front[back[i][j]].push_back(i);
// cout << back[i][j] << " to " << i << " relationship" << '\n';
// }
}
for (long long i=1; i<=n; i++)
visited[i]=0;
visited[a]=1;
q.push(a);
while (!q.empty())
{
long long u=q.front();
q.pop();
dp[0][u]=dist[1][u]+dist[2][u];
dp[1][u]=dist[1][u];
dp[2][u]=dist[2][u];
for (long long i=0; i<back[u].size(); i++)
{
long long v=back[u][i];
dp[0][u]=min(dp[0][u], dp[0][v]);
// if (v==2)
// cout << "traverse " << dp[0][v] << " from " << v << " to " << u << '\n';
dp[1][u]=min(dp[1][u], dp[1][v]);
dp[2][u]=min(dp[2][u], dp[2][v]);
}
dp[0][u]=min(dp[0][u], min(dp[1][u]+dist[2][u], dp[2][u]+dist[1][u]));
// cout << "u " << u << ' ' << dp[1][u] << ' ' << dist[2][u] << ' ' << dp[2][u] << ' ' << dist[1][u] << ' ' << dp[0][u] << '\n';
for (long long i=0; i<front[u].size(); i++)
{
long long v=front[u][i];
if (!visited[v])
{
deg[v]--;
if (!deg[v])
{
visited[v]=1;
q.push(v);
}
}
}
}
cout << min(dp[0][b], dist[1][d]);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:38:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (long long i=0; i<adj[u].size(); i++)
| ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:93:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (long long i=0; i<back[u].size(); i++)
| ~^~~~~~~~~~~~~~~
commuter_pass.cpp:104:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (long long i=0; i<front[u].size(); i++)
| ~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
278 ms |
32932 KB |
Output is correct |
2 |
Correct |
293 ms |
32820 KB |
Output is correct |
3 |
Correct |
290 ms |
33236 KB |
Output is correct |
4 |
Correct |
301 ms |
33736 KB |
Output is correct |
5 |
Correct |
295 ms |
33464 KB |
Output is correct |
6 |
Correct |
291 ms |
32840 KB |
Output is correct |
7 |
Correct |
287 ms |
33400 KB |
Output is correct |
8 |
Correct |
292 ms |
33268 KB |
Output is correct |
9 |
Correct |
279 ms |
33076 KB |
Output is correct |
10 |
Correct |
243 ms |
33092 KB |
Output is correct |
11 |
Correct |
143 ms |
26080 KB |
Output is correct |
12 |
Correct |
286 ms |
33596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
290 ms |
32568 KB |
Output is correct |
2 |
Correct |
292 ms |
32320 KB |
Output is correct |
3 |
Correct |
301 ms |
32316 KB |
Output is correct |
4 |
Correct |
293 ms |
32316 KB |
Output is correct |
5 |
Correct |
304 ms |
32408 KB |
Output is correct |
6 |
Correct |
273 ms |
33380 KB |
Output is correct |
7 |
Correct |
294 ms |
33144 KB |
Output is correct |
8 |
Correct |
296 ms |
32316 KB |
Output is correct |
9 |
Correct |
304 ms |
32344 KB |
Output is correct |
10 |
Correct |
308 ms |
32320 KB |
Output is correct |
11 |
Correct |
140 ms |
26084 KB |
Output is correct |
12 |
Correct |
276 ms |
33288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9292 KB |
Output is correct |
2 |
Correct |
4 ms |
7372 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
17 ms |
11220 KB |
Output is correct |
5 |
Correct |
10 ms |
9048 KB |
Output is correct |
6 |
Correct |
4 ms |
7504 KB |
Output is correct |
7 |
Correct |
5 ms |
7564 KB |
Output is correct |
8 |
Correct |
5 ms |
7628 KB |
Output is correct |
9 |
Correct |
5 ms |
7500 KB |
Output is correct |
10 |
Correct |
11 ms |
9044 KB |
Output is correct |
11 |
Correct |
4 ms |
7372 KB |
Output is correct |
12 |
Correct |
4 ms |
7424 KB |
Output is correct |
13 |
Correct |
4 ms |
7372 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
5 ms |
7500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
278 ms |
32932 KB |
Output is correct |
2 |
Correct |
293 ms |
32820 KB |
Output is correct |
3 |
Correct |
290 ms |
33236 KB |
Output is correct |
4 |
Correct |
301 ms |
33736 KB |
Output is correct |
5 |
Correct |
295 ms |
33464 KB |
Output is correct |
6 |
Correct |
291 ms |
32840 KB |
Output is correct |
7 |
Correct |
287 ms |
33400 KB |
Output is correct |
8 |
Correct |
292 ms |
33268 KB |
Output is correct |
9 |
Correct |
279 ms |
33076 KB |
Output is correct |
10 |
Correct |
243 ms |
33092 KB |
Output is correct |
11 |
Correct |
143 ms |
26080 KB |
Output is correct |
12 |
Correct |
286 ms |
33596 KB |
Output is correct |
13 |
Correct |
290 ms |
32568 KB |
Output is correct |
14 |
Correct |
292 ms |
32320 KB |
Output is correct |
15 |
Correct |
301 ms |
32316 KB |
Output is correct |
16 |
Correct |
293 ms |
32316 KB |
Output is correct |
17 |
Correct |
304 ms |
32408 KB |
Output is correct |
18 |
Correct |
273 ms |
33380 KB |
Output is correct |
19 |
Correct |
294 ms |
33144 KB |
Output is correct |
20 |
Correct |
296 ms |
32316 KB |
Output is correct |
21 |
Correct |
304 ms |
32344 KB |
Output is correct |
22 |
Correct |
308 ms |
32320 KB |
Output is correct |
23 |
Correct |
140 ms |
26084 KB |
Output is correct |
24 |
Correct |
276 ms |
33288 KB |
Output is correct |
25 |
Correct |
10 ms |
9292 KB |
Output is correct |
26 |
Correct |
4 ms |
7372 KB |
Output is correct |
27 |
Correct |
4 ms |
7380 KB |
Output is correct |
28 |
Correct |
17 ms |
11220 KB |
Output is correct |
29 |
Correct |
10 ms |
9048 KB |
Output is correct |
30 |
Correct |
4 ms |
7504 KB |
Output is correct |
31 |
Correct |
5 ms |
7564 KB |
Output is correct |
32 |
Correct |
5 ms |
7628 KB |
Output is correct |
33 |
Correct |
5 ms |
7500 KB |
Output is correct |
34 |
Correct |
11 ms |
9044 KB |
Output is correct |
35 |
Correct |
4 ms |
7372 KB |
Output is correct |
36 |
Correct |
4 ms |
7424 KB |
Output is correct |
37 |
Correct |
4 ms |
7372 KB |
Output is correct |
38 |
Correct |
4 ms |
7500 KB |
Output is correct |
39 |
Correct |
5 ms |
7500 KB |
Output is correct |
40 |
Correct |
243 ms |
32688 KB |
Output is correct |
41 |
Correct |
273 ms |
32824 KB |
Output is correct |
42 |
Correct |
281 ms |
32828 KB |
Output is correct |
43 |
Correct |
130 ms |
26152 KB |
Output is correct |
44 |
Correct |
130 ms |
26188 KB |
Output is correct |
45 |
Correct |
337 ms |
33976 KB |
Output is correct |
46 |
Correct |
311 ms |
33596 KB |
Output is correct |
47 |
Correct |
305 ms |
34424 KB |
Output is correct |
48 |
Correct |
136 ms |
25668 KB |
Output is correct |
49 |
Correct |
238 ms |
34108 KB |
Output is correct |
50 |
Correct |
279 ms |
33720 KB |
Output is correct |
51 |
Correct |
282 ms |
33776 KB |
Output is correct |