#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define vt vector
#define heap priority_queue
#define dq deque
#define maxN 100005
#define maxM 5005
#define fi first
#define se second
#define For(i, j, n) for(int i=(j);i<=(n);i++)
#define pb push_back
#define pf push_front
#define reset(x,val) memset((x),(val),sizeof(x))
#define bit(i,j) ((i>>j)&1ll)
#define mask(i) (1ll<<i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define inf 10000000007 // mod for some cases
void io() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
typedef int ll;
typedef pair<ll, ll> ii;
//type_here
struct pp
{
ll u, dd;
};
struct pp2
{
ll u, dd, t;
};
struct cmp
{
bool operator()(pp a, pp b)
{
return a.dd>b.dd;
};
};
struct cmp2
{
bool operator()(pp2 a, pp2 b)
{
return a.dd>b.dd;
}
};
heap <pp, vt<pp>, cmp> h;
heap <pp2, vt<pp2>, cmp2> h2;
ll n, m, d1[maxN], c1[maxN], d2[maxM][maxM];
map<ii, ll> d;
ll s, t, u, v;
ll ans, cnt;
vt<ll> a[maxN], w[maxN];
void dj1(ll s)
{
reset(d1, inf);
d1[s] = 0;
h.push({s, d1[s]});
while(!h.empty())
{
pp x = h.top(); h.pop();
ll u = x.u;
ll wee = x.dd;
if (wee!=d1[u]) continue;
for (int i=0;i<a[u].size();i++)
{
ll v = a[u][i], we = w[u][i];
//cout<<u<<" "<<v<<endl;
if (d1[v]>d1[u] + we)
{
d1[v]=d1[u] + we;
c1[v]=1;
h.push({v, d1[v]});
}
else if (d1[v]==d1[u] + we)
{
c1[v]++;
}
}
}
}
void trace(ll u)
{
if (u==s) {cnt--; return;}
for (int i=0;i<a[u].size();i++)
{
ll v = a[u][i], we = w[u][i];
if (d1[v]+we==d1[u])
{
d[{u, v}] = d[{v, u}] = cnt;
//cout<<u<<" "<<v<<" "<<cnt<<" "<<00000<<endl;
trace(v);
}
}
}
void dj2(ll s)
{
reset(d2, inf);
d2[s][0] = 0;
h2.push({s, d2[s][0], 0});
while(!h2.empty())
{
pp2 x = h2.top(); h2.pop();
ll u = x.u;
ll wee = x.dd;
ll typ = x.t;
if (d2[u][typ]!=wee) continue;
For (i, 0, a[u].size()-1)
{
ll v = a[u][i], we = w[u][i];
ll ntyp = d[{u, v}];
For (ti, 1, ans)
{
if (ti==ntyp&&ntyp)
{
if (d2[v][ntyp]>d2[u][typ])
{
d2[v][ntyp]=d2[u][typ];
h2.push({v, d2[v][ntyp], ntyp});
}
}
else
{
if (d2[v][ti]>d2[u][typ]+we)
{
d2[v][ti]=d2[u][typ]+we;
h2.push({v, d2[v][ti]+we, ti});
}
}
//cout<<u<<" "<<v<<" "<<d2[v][ti]<<" "<<ti<<endl;
}
}
}
}
void solve()
{
cin>>n>>m;
cin>>s>>t;
cin>>u>>v;
For (i, 1, m)
{
ll x, y, c;
cin>>x>>y>>c;
a[x].pb(y);
a[y].pb(x);
w[x].pb(c);
w[y].pb(c);
}
dj1(s);
cnt = ans = c1[t];
//cout<<c1[t]<<endl;
while(cnt)
{
trace(t);
}
//cout<<000000<<endl;
dj2(u);
ll res = inf;
For (i, 0, ans)
{
res = min(res, d2[v][i]);
}
cout<<res<<endl;
}
signed main()
{
io();
solve();
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dj1(ll)':
commuter_pass.cpp:19:13: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000007' to '1410065415' [-Woverflow]
19 | #define inf 10000000007 // mod for some cases
| ^
commuter_pass.cpp:14:34: note: in definition of macro 'reset'
14 | #define reset(x,val) memset((x),(val),sizeof(x))
| ^~~
commuter_pass.cpp:55:15: note: in expansion of macro 'inf'
55 | reset(d1, inf);
| ^~~
commuter_pass.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i=0;i<a[u].size();i++)
| ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void trace(ll)':
commuter_pass.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i=0;i<a[u].size();i++)
| ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dj2(ll)':
commuter_pass.cpp:19:13: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000007' to '1410065415' [-Woverflow]
19 | #define inf 10000000007 // mod for some cases
| ^
commuter_pass.cpp:14:34: note: in definition of macro 'reset'
14 | #define reset(x,val) memset((x),(val),sizeof(x))
| ^~~
commuter_pass.cpp:97:15: note: in expansion of macro 'inf'
97 | reset(d2, inf);
| ^~~
commuter_pass.cpp:11:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define For(i, j, n) for(int i=(j);i<=(n);i++)
| ^
commuter_pass.cpp:107:9: note: in expansion of macro 'For'
107 | For (i, 0, a[u].size()-1)
| ^~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:19:13: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '10000000007' to '1410065415' [-Woverflow]
19 | #define inf 10000000007 // mod for some cases
| ^~~~~~~~~~~
commuter_pass.cpp:157:14: note: in expansion of macro 'inf'
157 | ll res = inf;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
228648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
275 ms |
242364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
104280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
228648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
