| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 132478 | ksmzzang2003 | Commuter Pass (JOI18_commuter_pass) | C11 | 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 INF (1LL<<60)
typedef long long ll;
typedef pair <int,int> pii;
int N,M,S,T,U,V,deg[101010];
ll du[101010],dv[101010],d[101010],disu[101010],disv[101010],dist[101010];
vector <pii> adj[101010];
vector <pii> dag[101010];
struct data{
int u,v ; ll w ;
bool operator<(const data &r)const{
return w>r.w;
}
};
priority_queue <data> pq;
queue <int> q;
int main(){
scanf("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
for(int i=1;i<=M;i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
adj[u].push_back(pii(v,w));
adj[v].push_back(pii(u,w));
}
for(int i=1;i<=N;i++) dist[i] = INF;
pq.push(data{0,S,0});
while(!pq.empty()){
data t = pq.top(); pq.pop();
if(t.w<=dist[t.v]) deg[t.v]++, dag[t.u].push_back(t.v);
if(t.w>=dist[t.v]) continue;
dist[t.v] = t.w;
for(pii nx: adj[t.v]) pq.push((data){t.v,nx.first,nx.second+t.w});
}
for(int i=1;i<=N;i++) disv[i] = INF;
pq.push(data{0,V,0});
while(!pq.empty()){
data t = pq.top();
pq.pop();
if(t.w>=disv[t.v]) continue;
distv[t.v] = t.w;
for(pii nx:adj[t.v]) pq.push((data){t.v,nx.first,nx.second+t.w});
}
q.push(S);
for(int i=1;i<=N;i++) du[i] = disu[i],dv[i] = disv[i],d[i] = INF;
while(!q.empty()){
int u = q.front(); q.pop();
d[u] = min(d[u],du[u]+disv[u]);
d[u] = min(d[u],dv[u]+disu[u]);
for(int v:dag[u]){
d[v] = min(d[v],d[u]);
du[v] = min(du[v],du[u]);
dv[v] = min(dv[v],dv[u]);
deg[v]--; if(deg[v]==0) q.push(v);
}
}
printf("%lld",min(d[T],disu[v]));
}