이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///0-0 : what is your motivation, quan606303?
///quan606303 : Hutao
/*idea :
*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=100000+7;
bool vst[maxn];
int dis_S[maxn],dis_T[maxn],dis_U[maxn],dis_V[maxn],n,m;
vector<pair<int,int> > adj[maxn];
void dij(int x,int *dis)
{
for (int i=1;i<=n;i++)dis[i]=1e18,vst[i]=false;
dis[x]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.push({0,x});
while (q.size())
{
pair<int,int> cnt=q.top();
q.pop();
if (vst[cnt.se])continue;
vst[cnt.se]=true;
for (auto i:adj[cnt.se])
{
if (dis[i.fi]>dis[cnt.se]+i.se)
{
dis[i.fi]=dis[cnt.se]+i.se;
q.push({dis[i.fi],i.fi});
}
}
}
}
int s,t,u,v,dp[maxn][2];
bool cmp(int x,int y)
{
return dis_S[x]<dis_S[y];
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//file("");
cin>>n>>m>>s>>t>>u>>v;
for (int i=1;i<=m;i++)
{
int x,y,w;
cin>>x>>y>>w;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
dij(s,dis_S);
dij(t,dis_T);
dij(u,dis_U);
dij(v,dis_V);
vector<int> vt;
for (int i=1;i<=n;i++)vt.push_back(i),dp[i][0]=dp[i][1]=1e18;
sort(vt.begin(),vt.end(),cmp);
int res=dis_U[v];
for (auto i:vt)
{
if (dis_S[i]+dis_T[i]==dis_S[t])
{
dp[i][0]=dis_U[i];
dp[i][1]=dis_V[i];
for (auto j:adj[i])
{
if (dis_S[j.fi]+j.se==dis_S[i])
{
dp[i][0]=min(dp[i][0],dp[j.fi][0]);
dp[i][1]=min(dp[i][1],dp[j.fi][1]);
}
}
res=min({res,dp[i][0]+dis_V[i],dp[i][1]+dis_U[i]});
}
}
cout<<res;
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... |