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