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[305],rraph[305];
vector<ll> trace[305];
ll u[200005],v[200005],w[200005],d[305],d1[305],dlast[305];
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(100005);
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;
}
dijkstra(y);
ll ans=d[x];
for(int i=1;i<=n;i++) if(check[i]) ans=min(ans,d[i]);
cout << ans << endl;
}
void dijkstratrace(ll s)
{
memset(d,0x3f,sizeof(d));
d[s]=0;
trace[s]={1};
priority_queue<llll,vector<llll>,greater<llll>> pq;
pq.push({d1[s],s});
while(pq.size())
{
ll u=pq.top().se;
pq.pop();
vector<ll> temp=trace[u];
for(int i=0;i<rraph[u].size();i++)
{
ll v=rraph[u][i].fi,w=rraph[u][i].se;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
pq.push({d[v],v});
for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
}
else if(d[v]==d[u]+w) for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
}
trace[u]=temp;
}
}
void dijkstralast(ll s,ll k)
{
memset(dlast,0x3f,sizeof(dlast));
dlast[s]=0;
priority_queue<llll,vector<llll>,greater<llll>> pq;
pq.push({dlast[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(trace[u].size()&&trace[u].back()>=k&&trace[v].size()&&trace[v].back()>=k)
{
if(*lower_bound(trace[u].begin(),trace[u].end(),k)==k&&*lower_bound(trace[v].begin(),trace[v].end(),k)==k) w=0;
}
if(dlast[v]>dlast[u]+w)
{
dlast[v]=dlast[u]+w;
pq.push({dlast[v],v});
}
}
}
}
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;
}
dijkstra(s);
dijkstra1(t);
for(int i=1;i<=m;i++)
{
if(d[u[i]]+d1[v[i]]+w[i]==d[t])
{
rraph[u[i]].push_back({v[i],w[i]});
rraph[v[i]].push_back({u[i],w[i]});
}
if(d[v[i]]+d1[u[i]]+w[i]==d[t])
{
rraph[u[i]].push_back({v[i],w[i]});
rraph[v[i]].push_back({u[i],w[i]});
}
}
dijkstratrace(s);
for(int i=1;i<=n;i++)
{
sort(trace[i].begin(),trace[i].end());
}
ll ans=INFINITE2;
for(int i=1;i<=trace[t].size();i++)
{
dijkstralast(x,i);
ans=min(ans,dlast[y]);
}
cout << ans << endl;
}
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:57: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]
57 | for(int i=0;i<graph[u].size();i++)
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(ll)':
commuter_pass.cpp:79: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]
79 | for(int i=0;i<graph[u].size();i++)
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstratrace(ll)':
commuter_pass.cpp:119: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]
119 | for(int i=0;i<rraph[u].size();i++)
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:126:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:128:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | else if(d[v]==d[u]+w) for(int i=0;i<trace[u].size();i++) trace[v].push_back(trace[u][i]++);
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstralast(ll, ll)':
commuter_pass.cpp:144: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]
144 | for(int i=0;i<graph[u].size();i++)
| ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for(int i=1;i<=trace[t].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... |