#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define xx first
#define yy second
#define MAXN 100010
#define INF 1000000000000000LL
#define MALON 310
using namespace std;
ll n, m, s, t, x, y, d[MAXN], ds[MAXN], dt[MAXN], dy[MAXN], p[MAXN], fw[MALON][MALON], ress=INF;
vector<ll> g[MAXN];
map<pii, ll> w;
void dijkstra(int s, ll d[])
{
for (int i=1; i<=n; i++) { d[i]=INF; p[i]=-1; }
priority_queue< pll, vector<pll>, greater<pll> > pq;
pq.push({0, s});
d[s]=0;
p[s]=-1;
while (!pq.empty())
{
ll td=pq.top().xx, u=pq.top().yy;
pq.pop();
if (td!=d[u]) continue;
for (int i=0; i<g[u].size(); i++)
{
ll v, ww;
v=g[u][i];
pii par={u, v};
ww=w[par];
if (d[u]+ww<d[v])
{
d[v]=d[u]+ww;
p[v]=u;
pq.push({d[v], v});
}
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>s>>t>>x>>y;
for (int i=0; i<m; i++)
{
int u, v, ww; cin>>u>>v>>ww;
g[u].pb(v);
g[v].pb(u);
w[{u, v}]=ww;
w[{v, u}]=ww;
}
if (s==x)
{
dijkstra(s, ds); dijkstra(t, dt); dijkstra(y, dy);
ress=ds[y];
for (int i=1; i<=n; i++) if ((ds[i]+dt[i])==ds[t]) ress=min(ress, dy[i]);
cout<<ress;
exit(0);
}
if (n<=300)
{
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) fw[i][j]=INF;
for (int i=1; i<=n; i++)
{
fw[i][i]=0;
for (int j=0; j<g[i].size(); j++) fw[i][g[i][j]]=w[{i, g[i][j]}];
}
for (int v=1; v<=n; v++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
fw[i][j]=min(fw[i][j], fw[i][v]+fw[v][j]);
//for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cout<<i<<" "<<j<<" "<<fw[i][j]<<endl;
ress=fw[x][y];
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (fw[s][i]+fw[i][j]+fw[j][t]==fw[s][t]) ress=min(ress, min(fw[x][i]+fw[j][y], fw[x][j]+fw[i][y]));
}
}
cout<<ress;
exit(0);
}
dijkstra(s, d);
//cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<" "<<d[5]<<" "<<d[6]<<endl;
int u=t;
while(p[u]!=-1)///p[u] ili u?
{
//cout<<u<<" "<<p[u]<<endl;
w[{u, p[u]}]=0;
w[{p[u], u}]=0;
u=p[u];
}
dijkstra(x, d);
//cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<" "<<d[5]<<" "<<d[6];
cout<<d[y];
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(int, long long int*)':
commuter_pass.cpp:35:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i=0; i<g[u].size(); i++)
| ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:82:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j=0; j<g[i].size(); j++) fw[i][g[i][j]]=w[{i, g[i][j]}];
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1264 ms |
40436 KB |
Output is correct |
2 |
Correct |
1238 ms |
39344 KB |
Output is correct |
3 |
Correct |
1303 ms |
42604 KB |
Output is correct |
4 |
Correct |
1281 ms |
43228 KB |
Output is correct |
5 |
Correct |
1238 ms |
42540 KB |
Output is correct |
6 |
Correct |
1265 ms |
44520 KB |
Output is correct |
7 |
Correct |
1239 ms |
42708 KB |
Output is correct |
8 |
Correct |
1277 ms |
42556 KB |
Output is correct |
9 |
Correct |
1270 ms |
43728 KB |
Output is correct |
10 |
Correct |
1073 ms |
43476 KB |
Output is correct |
11 |
Correct |
559 ms |
23676 KB |
Output is correct |
12 |
Correct |
1256 ms |
43456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1081 ms |
38864 KB |
Output is correct |
2 |
Correct |
1068 ms |
40464 KB |
Output is correct |
3 |
Correct |
1070 ms |
41780 KB |
Output is correct |
4 |
Correct |
1058 ms |
40612 KB |
Output is correct |
5 |
Correct |
1090 ms |
40784 KB |
Output is correct |
6 |
Correct |
1101 ms |
40696 KB |
Output is correct |
7 |
Correct |
1100 ms |
41780 KB |
Output is correct |
8 |
Correct |
1067 ms |
40852 KB |
Output is correct |
9 |
Correct |
1078 ms |
41880 KB |
Output is correct |
10 |
Correct |
1054 ms |
41008 KB |
Output is correct |
11 |
Correct |
505 ms |
21996 KB |
Output is correct |
12 |
Correct |
1114 ms |
40584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
6892 KB |
Output is correct |
2 |
Correct |
40 ms |
3564 KB |
Output is correct |
3 |
Correct |
35 ms |
3564 KB |
Output is correct |
4 |
Correct |
124 ms |
10340 KB |
Output is correct |
5 |
Correct |
64 ms |
6764 KB |
Output is correct |
6 |
Correct |
36 ms |
3820 KB |
Output is correct |
7 |
Correct |
37 ms |
3820 KB |
Output is correct |
8 |
Correct |
41 ms |
4076 KB |
Output is correct |
9 |
Correct |
36 ms |
3820 KB |
Output is correct |
10 |
Correct |
71 ms |
6892 KB |
Output is correct |
11 |
Correct |
34 ms |
3436 KB |
Output is correct |
12 |
Correct |
35 ms |
3436 KB |
Output is correct |
13 |
Correct |
35 ms |
3564 KB |
Output is correct |
14 |
Correct |
35 ms |
3564 KB |
Output is correct |
15 |
Correct |
36 ms |
3564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1264 ms |
40436 KB |
Output is correct |
2 |
Correct |
1238 ms |
39344 KB |
Output is correct |
3 |
Correct |
1303 ms |
42604 KB |
Output is correct |
4 |
Correct |
1281 ms |
43228 KB |
Output is correct |
5 |
Correct |
1238 ms |
42540 KB |
Output is correct |
6 |
Correct |
1265 ms |
44520 KB |
Output is correct |
7 |
Correct |
1239 ms |
42708 KB |
Output is correct |
8 |
Correct |
1277 ms |
42556 KB |
Output is correct |
9 |
Correct |
1270 ms |
43728 KB |
Output is correct |
10 |
Correct |
1073 ms |
43476 KB |
Output is correct |
11 |
Correct |
559 ms |
23676 KB |
Output is correct |
12 |
Correct |
1256 ms |
43456 KB |
Output is correct |
13 |
Correct |
1081 ms |
38864 KB |
Output is correct |
14 |
Correct |
1068 ms |
40464 KB |
Output is correct |
15 |
Correct |
1070 ms |
41780 KB |
Output is correct |
16 |
Correct |
1058 ms |
40612 KB |
Output is correct |
17 |
Correct |
1090 ms |
40784 KB |
Output is correct |
18 |
Correct |
1101 ms |
40696 KB |
Output is correct |
19 |
Correct |
1100 ms |
41780 KB |
Output is correct |
20 |
Correct |
1067 ms |
40852 KB |
Output is correct |
21 |
Correct |
1078 ms |
41880 KB |
Output is correct |
22 |
Correct |
1054 ms |
41008 KB |
Output is correct |
23 |
Correct |
505 ms |
21996 KB |
Output is correct |
24 |
Correct |
1114 ms |
40584 KB |
Output is correct |
25 |
Correct |
65 ms |
6892 KB |
Output is correct |
26 |
Correct |
40 ms |
3564 KB |
Output is correct |
27 |
Correct |
35 ms |
3564 KB |
Output is correct |
28 |
Correct |
124 ms |
10340 KB |
Output is correct |
29 |
Correct |
64 ms |
6764 KB |
Output is correct |
30 |
Correct |
36 ms |
3820 KB |
Output is correct |
31 |
Correct |
37 ms |
3820 KB |
Output is correct |
32 |
Correct |
41 ms |
4076 KB |
Output is correct |
33 |
Correct |
36 ms |
3820 KB |
Output is correct |
34 |
Correct |
71 ms |
6892 KB |
Output is correct |
35 |
Correct |
34 ms |
3436 KB |
Output is correct |
36 |
Correct |
35 ms |
3436 KB |
Output is correct |
37 |
Correct |
35 ms |
3564 KB |
Output is correct |
38 |
Correct |
35 ms |
3564 KB |
Output is correct |
39 |
Correct |
36 ms |
3564 KB |
Output is correct |
40 |
Correct |
1077 ms |
43208 KB |
Output is correct |
41 |
Correct |
1034 ms |
42100 KB |
Output is correct |
42 |
Correct |
1041 ms |
42028 KB |
Output is correct |
43 |
Correct |
536 ms |
22124 KB |
Output is correct |
44 |
Incorrect |
536 ms |
21996 KB |
Output isn't correct |
45 |
Halted |
0 ms |
0 KB |
- |