This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
,
,. | \
|: \ ; :\
:' ;\| ::\
\ : | `::\
_) | `:`.
,' , `. ;: ;
,' ;: ;"' ,:: |_
/, ` . ;::: |:`-.__
_,' _o\ ,::.`:' ; ; . '
_,-' `:. ;""\,
,-' ,: `-;,
\, ;: ;--._
`.______,-,----._ ,' ;: ,/ , ,`
/ /,-';' \ ; `: ,'/,::.:::
,',;-'-'_,--; ; :. ,',',;::::::
( /___,-' `. ;::,,'o/ ,:::::::
`' ) ;:,'o / ;"- -::
\__ _,'o ,' ,::
) `--' ,..::::
_lftroq_ ; `. ,:::::::
; ``::. :::::::
*/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007LL
#define MOD2 998244353LL
#define endl '\n'
#define INFINITE 2147483647LL
#define INFINITE2 9223372036854775807
#define llll pair<ll,ll>
#define ldld pair<ld,ld>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
ll n,m,s,t,x,y;
vector<llll> graph[200005];
ll u[200005],v[200005],w[200005],d[200005],d1[200005];
void dijkstra(ll s)
{
memset(d,0x3f,sizeof(d));
d[s]=0;
priority_queue<llll,vector<llll>,greater<llll>> pq;
pq.push({d[s],s});
while(pq.size())
{
ll u=pq.top().se;
pq.pop();
for(int i=0;i<graph[u].size();i++)
{
ll v=graph[u][i].fi,w=graph[u][i].se;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
pq.push({d[v],v});
}
}
}
}
void dijkstra1(ll s)
{
memset(d1,0x3f,sizeof(d1));
d1[s]=0;
priority_queue<llll,vector<llll>,greater<llll>> pq;
pq.push({d1[s],s});
while(pq.size())
{
ll u=pq.top().se;
pq.pop();
for(int i=0;i<graph[u].size();i++)
{
ll v=graph[u][i].fi,w=graph[u][i].se;
if(d1[v]>d1[u]+w)
{
d1[v]=d1[u]+w;
pq.push({d1[v],v});
}
}
}
}
void solve1()
{
dijkstra(s);
dijkstra1(t);
vector<bool> check(200005);
for(int i=1;i<=m;i++)
{
if(d[u[i]]+d1[v[i]]+w[i]==d[t]) check[u[i]]=check[v[i]]=true;
if(d[v[i]]+d1[u[i]]+w[i]==d[t]) check[u[i]]=check[v[i]]=true;
}
ll ans=0x3f;
dijkstra(y);
for(int i=1;i<=n;i++) if(check[i]) ans=min(ans,d[i]);
cout << ans << endl;
}
void solve()
{
cin >> n >> m >> s >> t >> x >> y;
for(int i=1;i<=m;i++)
{
cin >> u[i] >> v[i] >> w[i];
graph[u[i]].push_back({v[i],w[i]});
graph[v[i]].push_back({u[i],w[i]});
}
if(s==x)
{
solve1();
return;
}
if(s==y)
{
swap(x,y);
solve1();
return;
}
}
int main()
{
fastIO
//freopen("hanhhhh.inp","r",stdin);
//freopen("hanhhhh.out","w",stdout);
ll t=1;
//cin >> t;
while(t--)
solve();
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void dijkstra(ll)':
commuter_pass.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<graph[u].size();i++)
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(ll)':
commuter_pass.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<graph[u].size();i++)
| ~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |