이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxm=200000+10;
struct yal{
long long u,v,w,te,dov;
long long getad(long long fu){
long long ret=(u^v^fu);
return ret;
}
};
yal alled[maxm];
vector<long long>adj[maxn];
long long dis[maxn];
long long inf=1e15;
long long n,m,s,t,fu,fv,vis[maxn];
void firstdij(){
set<pair<long long,pair<long long,long long>>>st;
for(auto x:adj[s]){
st.insert(make_pair(alled[x].w,make_pair(alled[x].getad(s),x)));
}
dis[s]=0;
while((long long)st.size()>0){
auto x=*st.begin();
st.erase(x);
if(x.first>dis[x.second.first]){
continue;
}
alled[x.second.second].dov=1;
dis[x.second.first]=x.first;
if(alled[x.second.second].u==x.second.first){
swap(alled[x.second.second].u,alled[x.second.second].v);
}
for(auto y:adj[x.second.first]){
st.insert(make_pair(alled[y].w+x.first,make_pair(alled[y].getad(x.second.first),y)));
}
}
}
void dfs(long long u){
if(vis[u]==1){
return ;
}
vis[u]=1;
for(auto x:adj[u]){
if(alled[x].v==u&&alled[x].dov==1){
alled[x].te=1;
dfs(alled[x].u);
}
}
}
long long visd[maxn][5];
long long dij(){
set<pair<long long ,pair<long long,long long>>>st;
st.insert(make_pair(0,make_pair(fu,0)));
while((long long)st.size()>0){
auto x=*st.begin();
st.erase(x);
// cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<"\n";
if(visd[x.second.first][x.second.second]==1){
continue;
}
visd[x.second.first][x.second.second]=1;
if(x.second.first==fv){
return x.first;
}
for(auto y:adj[x.second.first]){
if(alled[y].te){
if(x.second.second==0){
if(alled[y].u==x.second.first){
st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
}
else{
st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
}
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),0)));
}
if(x.second.second==1){
if(alled[y].u==x.second.first){
st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
}
else{
// st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
}
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
}
if(x.second.second==2){
if(alled[y].u==x.second.first){
// st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
}
else{
st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
}
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
}
if(x.second.second==3){
if(alled[y].u==x.second.first){
// st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
}
else{
// st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
}
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
}
}
else{
if(x.second.second==0){
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),0)));
}
if(x.second.second==1){
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
}
if(x.second.second==2){
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
}
if(x.second.second==3){
st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
}
}
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(long long i=0;i<maxn;i++){
dis[i]=inf;
}
cin>>n>>m;
cin>>s>>t;
cin>>fu>>fv;
for(long long i=0;i<m;i++){
cin>>alled[i].u>>alled[i].v>>alled[i].w;
adj[alled[i].u].push_back(i);
adj[alled[i].v].push_back(i);
}
firstdij();
//cout<<"salam"<<endl;
dfs(t);
cout<<dij()<<"\n";
}
# | 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... |