이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n , m , s , t , ss , tt , dis[2][N] , slm[3][N];
vector <pair<int , int>> adj[N];
bool marked[N];
void dij(int star , int h[])
{
memset(h , 63 , sizeof (dis[0])); memset(marked , false , sizeof marked);
h[star] = 0;
priority_queue <pair<int , int>> pq;
pq.push({0 , star});
while(!pq.empty())
{
auto now = pq.top(); pq.pop();
int v = now.second , D = abs(now.first);
if(marked[v])
continue;
marked[v] = true;
for(auto u : adj[v]) if(h[u.first] > D + u.second)
{
h[u.first] = D + u.second;
pq.push({-h[u.first] , u.first});
}
}
}
bool mrk[3][N];
void solve(int star)
{
memset(slm , 63 , sizeof slm);
memset(mrk , false , sizeof mrk);
slm[0][star] = 0;
priority_queue <pair<int , pair<int , int>>> pq;
pq.push({0 , {0 , star}});
while(!pq.empty())
{
auto now = pq.top(); pq.pop();
int v = now.second.second , ty = now.second.first , D = abs(now.first);
if(mrk[ty][v])
continue;
mrk[ty][v] = true;
for(auto u : adj[v])
{
if(u.second == 0 && ty <= 1 && slm[1][u.first] > D)
{
slm[1][u.first] = D;
pq.push({-D , {1 , u.first}});
}
if(u.second > 0 && ty == 0 && slm[0][u.first] > D + u.second)
{
slm[0][u.first] = D + u.second;
pq.push({-slm[0][u.first] , {0 , u.first}});
}
if(u.second > 0 && ty >= 1 && slm[2][u.first] > D + u.second)
{
slm[2][u.first] = D + u.second;
pq.push({-slm[2][u.first] , {2 , u.first}});
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t >> ss >> tt;
assert(n <= N);
vector <pair<pair<int , int> , int>> edges;
while(m--)
{
int a , b , w;
cin >> a >> b >> w;
adj[a].push_back({b , w});
adj[b].push_back({a , w});
edges.push_back({{a , b} , w});
}
dij(s , dis[0]);
dij(t , dis[1]);
for(auto e : edges)
{
int a = e.first.first , b = e.first.second , w = e.second;
if(dis[0][a] + dis[1][b] + w == dis[0][t])
adj[a].push_back({b , 0});
if(dis[0][b] + dis[1][a] + w == dis[0][t])
adj[b].push_back({a , 0});
}
solve(ss);
int ans = min({slm[0][tt] , slm[1][tt] , slm[2][tt]});
solve(tt);
ans = min({ans , slm[0][ss] , slm[1][ss] , slm[2][ss]});
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... |