이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
long long n,m,s,t,a,b,ans;
vector<pair<long long, long long>> v[100005];
long long len[100005][4];
long long dp[100005][2];
void djikstra(int s, int nr)
{
for(int i=1;i<=n;i++)
len[i][nr] = 1e18;
multiset<pair<long long, long long>> mul;
mul.insert({0, s});
while(!mul.empty())
{
long long p = mul.begin()->second;
long long val = mul.begin()->first;
mul.erase(mul.begin());
if(len[p][nr] != 1e18)
continue;
len[p][nr] = val;
for(auto it : v[p])
{
if(len[it.first][nr] != 1e18)
continue;
mul.insert({val + it.second, it.first});
}
}
}
void calcDp0(int p)
{
if(dp[p][0] != 1e18)
return;
dp[p][0] = len[p][1];
for(auto it : v[p])
if(len[p][0] - it.second == len[it.first][0])
{
calcDp0(it.first);
dp[p][0] = min(dp[p][0], dp[it.first][0]);
}
}
void calcDp1(int p)
{
if(dp[p][1] != 1e18)
return;
dp[p][1] = len[p][1];
for(auto it : v[p])
if(len[p][0] + it.second == len[it.first][0] && dp[it.first][0] != 1e18)
{
calcDp1(it.first);
dp[p][1] = min(dp[p][1], dp[it.first][1]);
}
}
int main()
{
cin>>n>>m>>s>>t>>a>>b;
for(int i=1;i<=m;i++)
{
int x, y, c;
cin>>x>>y>>c;
v[x].push_back({y, c});
v[y].push_back({x, c});
}
djikstra(t, 0);
djikstra(b, 1);
djikstra(a, 2);
ans = len[a][1];
for(int i=1;i<=n;i++)
dp[i][0] = dp[i][1] = 1e18;
calcDp0(s);
calcDp1(t);
for(int i=1;i<=n;i++)
ans = min(ans, min(dp[i][0], dp[i][1]) + len[i][2]);
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... |