이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define p push
#define pii pair<int,int>
#define ppii pair<int,pii>
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define set(x) memset(x,-1,sizeof(x));
int n,m,s,t,u,v;
#define int long long
const int mxn=1e5,inf=LONG_LONG_MAX/2;
vector<pii>adj[mxn+10];
bitset<mxn+10>vis;
void dijk(int st,vector<int>&dist){
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.p({0,st});
dist[st]=0;
while(!pq.empty()){
int cur=pq.top().s;
pq.pop();
if(vis[cur])continue;
vis[cur]=true;
for(auto i:adj[cur]){
if(dist[i.f]>dist[cur]+i.s)dist[i.f]=dist[cur]+i.s,pq.p({dist[i.f],i.f});
}
}
vis.reset();
}
int32_t main(){
fastio
cin>>n>>m>>s>>t>>u>>v;
while(m--){
int a,b,c;cin>>a>>b>>c;
adj[a].pb({b,c});
adj[b].pb({a,c});
}
vector<int>dist1(n+1,inf);
vector<int>dist2(n+1,inf);
dijk(u,dist1);
dijk(v,dist2);
priority_queue<ppii,vector<ppii>,greater<ppii>>pq;
//dist cur pa
pq.p({0,{s,0}});
vector<pair<int,pii>>dist(n+1,{inf,{inf,inf}});
dist[s].f=0;
while(!pq.empty()){
int cur=pq.top().s.f,pa=pq.top().s.s,cd=pq.top().f;
pq.pop();
if(vis[cur]){
if(cd==dist[cur].f){
int cnu=min(dist1[cur],dist[pa].s.f),cnv=min(dist2[cur],dist[pa].s.s);
if(cnu+cnv<=dist[cur].s.f+dist[cur].s.s){
dist[cur].s.f=cnu;
dist[cur].s.s=cnv;
}
}
continue;
}
vis[cur]=true;
dist[cur].s.f=min(dist1[cur],dist[pa].s.f);
dist[cur].s.s=min(dist2[cur],dist[pa].s.s);
for(auto i:adj[cur]){
if(dist[i.f].f==-1||dist[i.f].f>=dist[cur].f+i.s){
int ndu=min(dist[cur].s.f,dist1[i.f]),ndv=min(dist[cur].s.s,dist2[i.f]);
dist[i.f]={dist[cur].f+i.s,{ndu,ndv}};
pq.p({dist[i.f].f,{i.f,cur}});
}
}
}
cout<<min(dist[t].s.f+dist[t].s.s,dist1[v]);
}
# | 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... |