| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1167699 | wstcube | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#pragma GCC optimize(O3,unroll-loops)
//#pragma GCC target(avx2,bmi,bmi2,popcnt,lzcnt)
#define ll long long
#define fi first
#define se second
#define pb push_back
const ll INF = 1000000000;
using namespace std;
ll n,m;
void dijkstra(vector<ll>& d,ll s, vector<vector<pair<ll,ll> > >& adj){
d.assign(n,INF);
d[s]=0;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >, greater<pair<ll,ll> > > q;
q.push({0,s});
while(!q.empty()){
ll v =q.top().se;
ll d_v = q.top().fi;
q.pop();
if(d[v]!=d_v)
continue;
for(auto edge : adj[v]){
ll to = edge.fi;
ll len = edge.se;
if(d[v] + len <d[to]){
d[to] = d[v]+len;
q.push({d[to],to});
}
}
}
}
ll main(){
std::ios_base::sync_with_stdio(0); cin.tie(0);
//ifstream cin("in.txt");
ll u,s,t,v;
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
vector<vector<pair<ll,ll> > > adj(n+1);
ll a,b,c;
for(ll i=0;i<m;i++){
cin >> a >> b >> c;
adj[a].pb({b,c});
adj[b].pb({a,c});
}
vector<ll> du(m),dt(m),ds(m),dv(m);
dijkstra(ds,s,adj);
dijkstra(dv,v,adj);
dijkstra(dt,t,adj);
ll res=-1;
for(ll i=1;i<=n;i++){
if(ds[i] + dt[i] == ds[t]){
if(res==-1) res = dv[i];
else if(res > dv[i]) res=dv[i];
}
}
cout << res;
return 0;
}