이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+10;
ll n,m,s,t,u,v,x[N],y[N],z[N],d1[N],d2[N],d3[N],d4[N],ans;
struct graph
{
ll cnt,dis[N],head[N],in[N],mind[N],v[N],f[N];
struct Edge
{
ll nx,to,cost;
}edg[N];
struct node
{
ll id,ans;
bool operator < (const node &x)const
{
return x.ans<ans;
}
};
void add(int a,int b,int c)
{
edg[++cnt].to=b;
edg[cnt].cost=c;
edg[cnt].nx=head[a];
in[b]++;
head[a]=cnt;
}
priority_queue<node> q;
void dj(int s,ll dis[])
{
for(int i=1;i<=n;i++)dis[i]=1ll*1e18;
memset(v,0,sizeof(v));
dis[s]=0;
q.push((node){s,0});
while(!q.empty())
{
node temp=q.top();
q.pop();
ll u=temp.id;
if(v[u])continue;
v[u]=1;
for(int j=head[u];j;j=edg[j].nx)
{
int to=edg[j].to;
if(dis[to]>dis[u]+edg[j].cost)
{
dis[to]=dis[u]+edg[j].cost;
if(!v[to])q.push((node){to,dis[to]});
}
}
}
}
void solve()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
mind[i]=d3[i];
if(!in[i])q.push(i);
}
while(!q.empty())
{
int x=q.front();q.pop();
if(f[x])continue;
f[x]=1;
ans=min(ans,mind[x]+d4[x]);
for(int j=head[x];j;j=edg[j].nx)
{
int v=edg[j].to;
in[v]--;mind[v]=min(mind[v],mind[x]);
if(!in[v])q.push(v);
}
}
}
}g1,g2,g3;
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m>>s>>t>>u>>v;
for(int i=1;i<=m;i++)
{
cin>>x[i]>>y[i]>>z[i];
g1.add(x[i],y[i],z[i]);
g1.add(y[i],x[i],z[i]);
}
g1.dj(s,d1);g1.dj(t,d2);g1.dj(u,d3);g1.dj(v,d4);
ans=d3[v];
for(int i=1;i<=m;i++)
{
if(d1[x[i]]+z[i]+d2[y[i]]==d1[t])g2.add(x[i],y[i],0),g3.add(y[i],x[i],0);
else if(d1[y[i]]+z[i]+d2[x[i]]==d1[t])g2.add(y[i],x[i],0),g3.add(x[i],y[i],0);
}
g2.solve();g3.solve();
cout<<ans<<'\n';
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... |