| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094246 | lamlamlam | Commuter Pass (JOI18_commuter_pass) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define pii pair<int,int>
const int MN = 2e5+5,inf = 1e18;
int n,m,a,b,c,d,u,v,w,dist[MN],dp[MN][4];
bool is_candidates[MN];
vector<int> trace[MN],g1[MN],g2[MN];
vector<pii> adj[MN];
void dickfather1(int x)
{
priority_queue<pii,vector<pii>,greater<pii>> pq;
for(int i=0; i<MN; i++) dist[i] = inf;
dist[x] = 0;
pq.push({0,x});
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
int d = tmp.first;
int u = tmp.second;
if(d!=dist[u]) continue;
for(auto y:adj[u]){
int v = y.first;
int len = y.second;
if(d+len<dist[v]){
trace[v].clear();
trace[v].push_back(u);
dist[v] = d+len;
pq.push({dist[v],v});
}
else if(d+len==dist[v]) trace[v].push_back(u);
}
}
}
bool vis[MN];
void dfs(int x)
{
is_candidates[x] = true;
vis[x] = true;
for(auto v:trace[x]) {
if(!vis[v]) dfs(v);
g1[x].push_back(v);
g2[v].push_back(x);
}
}
struct data
{
int d,v,phase;
bool operator < (const data &o) const
{
return d > o.d;
}
};
void dickfather2(int st)
{
for(int i=0; i<MN; i++) dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = inf;
priority_queue<data> pq;
dp[st][0] = 0;
pq.push({0,st,0});
while(!pq.empty())
{
auto tmp = pq.top();
pq.pop();
int d = tmp.d;
int v = tmp.v;
int phase = tmp.phase;
if(d!=dp[v][phase]) continue;
if(phase==0){
for(auto e:adj[v]){
int u = e.first;
int len = e.second;
if(d+len<dp[u][0]){
dp[u][0] = d + len;
pq.push({dp[u][0],u,0});
}
}
for(auto u:g1[v]) {
if(d<dp[u][1]){
dp[u][1] = d;
pq.push({dp[u][1],u,1});
}
}
for(auto u:g2[v]) {
if(d<dp[u][2]){
dp[u][2] = d;
pq.push({dp[u][2],u,2});
}
}
}
else if(phase==1){
for(auto e:adj[v]){
int u = e.first;
int len = e.second;
if(d+len<dp[u][3]){
dp[u][3] = d + len;
pq.push({dp[u][3],u,3});
}
}
for(auto u:g1[v]) {
if(d<dp[u][1]){
dp[u][1] = d;
pq.push({dp[u][1],u,1});
}
}
}
else if(phase==2){
for(auto e:adj[v]){
int u = e.first;
int len = e.second;
if(d+len<dp[u][3]){
dp[u][3] = d + len;
pq.push({dp[u][3],u,3});
}
}
for(auto u:g2[v]) {
if(d<dp[u][2]){
dp[u][2] = d;
pq.push({dp[u][2],u,2});
}
}
}
else{
for(auto e:adj[v]){
int u = e.first;
int len = e.second;
if(d+len<dp[u][3]){
dp[u][3] = d + len;
pq.push({dp[u][3],u,3});
}
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#define task "sus"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> m >> a >> b >> c >> d;
for(int i=1; i<=m; i++){
cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
dickfather1(a);
dfs(b);
dickfather2(c);
//for(int i=1; i<=n; i++) for(auto v:g2[i]) cout << i << ' ' << v << endl;
cout << min({dp[d][0],dp[d][1],dp[d][2],dp[d][3]});
cerr << "\nTime: " << clock() << endl;
}