이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define mp make_pair
const ll N = 1e5+7;
ll n,m,s,t,u,v;
vector<vector<pair<ll,ll>>> a;
vector<queue<ll>> from;
ll dis[N],len[N],flen[N];
void dijsktra1()
{
priority_queue<pair<ll,pair<ll,ll>>> pq;
pq.push(mp(0,mp(s,s)));
for(ll i = 0;i < n;i++){dis[i] = 1e18;len[i] = 0;flen[i] = 0;}
while(!pq.empty())
{
pair<ll,pair<ll,ll>> v = pq.top();
pq.pop();v.ff *= -1;
if(dis[v.ss.ff] < v.ff)continue;
len[v.ss.ff] = max(len[v.ss.ff],len[v.ss.ss] + 1);
if(dis[v.ss.ff] == v.ff){from[v.ss.ff].push(v.ss.ss);continue;}
dis[v.ss.ff] = v.ff;
from[v.ss.ff] = queue<ll>();
from[v.ss.ff].push(v.ss.ss);
for(auto x : a[v.ss.ff])pq.push(mp(-(x.ff+dis[v.ss.ff]),mp(x.ss,v.ss.ff)));
}
return ;
}
ll st[N];
void check()
{
queue<ll> q;
q.push(t);
while(!q.empty())
{
ll v = q.front();
q.pop();
if(st[v] == 1)continue;
st[v] = 1;flen[v] = len[v];
while(!from[v].empty())
{
q.push(from[v].front());
from[v].pop();
}
}
}
ll dis2[N],st2[N];
void dijsktra2()
{
priority_queue<pair<ll,pair<ll,ll>>> pq;
pq.push(mp(0,mp(u,-1)));
for(ll i = 0;i < n;i++)dis2[i] = 1e18;
for(ll i = 0;i < n;i++)st2[i] = 0;
while(!pq.empty())
{
pair<ll,pair<ll,ll>> v = pq.top();
pq.pop();v.ff *= -1;
if(st2[v.ss.ff] == -1)continue;
if(v.ss.ss == -1)st2[v.ss.ff] = -1;
else if((v.ss.ss == 0 || v.ss.ss == 1) && (st2[v.ss.ff] == 1 && st2[v.ss.ff] == 3))continue;
else if(v.ss.ss == -2 && (st2[v.ss.ff] == 2 || st2[v.ss.ff] == 3))continue;
else st2[v.ss.ff] += abs(v.ss.ss);
dis2[v.ss.ff] = min(v.ff,dis2[v.ss.ff]);
for(auto x : a[v.ss.ff])
{
if(st2[v.ss.ff] == -1)
{
if(flen[x.ss] != 0 && flen[v.ss.ff] != 0){
if(flen[x.ss] < flen[v.ss.ff])pq.push(mp(-(v.ff),mp(x.ss,0)));
else pq.push(mp(-(v.ff),mp(x.ss,1)));
}
pq.push(mp(-(v.ff+x.ff),mp(x.ss,-1)));
}
else if(st2[v.ss.ff] == 0)
{
if(flen[x.ss] != 0 && flen[v.ss.ff] != 0 && flen[x.ss] < flen[v.ss.ff])pq.push(mp(-(v.ff),mp(x.ss,0)));
else pq.push(mp(-(v.ff+x.ff),mp(x.ss,-2)));
}
else if(st2[v.ss.ff] == 1)
{
if(flen[x.ss] != 0 && flen[v.ss.ff] != 0 && flen[x.ss] > flen[v.ss.ff])pq.push(mp(-(v.ff),mp(x.ss,1)));
else pq.push(mp(-(v.ff+x.ff),mp(x.ss,-2)));
}
else pq.push(mp(-(v.ff+x.ff),mp(x.ss,-2)));
}
}
return ;
}
int main()
{
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m;
cin>>s>>t;s--;t--;
cin>>u>>v;u--;v--;
a.resize(n);from.resize(n);
for(ll i = 0;i < m;i++)
{
ll x,y,z;
cin>>x>>y>>z;x--;y--;
a[x].push_back(mp(z,y));
a[y].push_back(mp(z,x));
}
dijsktra1();
check();
dijsktra2();
cout<<dis2[v];
return 0;
}
# | 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... |