이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
using ll= long long;
#define fast_io ios::sync_with_stdio(0); cin.tie(0)
#define inpint(x) int x; cin>>x
#define inpll(x) long long x; cin>>x
#define fl(i, n) for(int i=0; i<n; i++)
#define flo(i, n) for(int i=1; i<=n; i++)
#define int long long
#define pi pair<int, int>
#define mp make_pair
#define ld long double
const int MOD = 7 + (int)1e9;
const int INF = (int)1e18;
//
void solve()
{
int n, m;
cin>>n>>m;
int s, t;
cin>>s>>t;
int u, v;
cin>>u>>v;
vector<vector<pi>> adjlist(n+1, vector<pi>(0));
for(int i=1; i<=m; i++)
{
int a, b, c;
cin>>a>>b>>c;
adjlist[a].pb({b, c});
adjlist[b].pb({a, c});
}
vector<int> vc(n+1, INF);
vector<int> uc(n+1, INF);
priority_queue<pi, vector<pi>, greater<pi>> pq;
uc[u] = 0;
vc[v] = 0;
pq.push({0, u});
while(not pq.empty())
{
int i = pq.top().second;
int c = pq.top().first;
pq.pop();
if(uc[i]<c) continue;
for(auto j: adjlist[i])
{
if(uc[j.first]<=c+j.second) continue;
uc[j.first] = c+j.second;
pq.push({uc[j.first], j.first});
}
}
pq.push({0, v});
while(not pq.empty())
{
int i = pq.top().second;
int c = pq.top().first;
pq.pop();
if(vc[i]<c) continue;
for(auto j: adjlist[i])
{
if(vc[j.first]<=c+j.second) continue;
vc[j.first] = c+j.second;
pq.push({vc[j.first], j.first});
}
}
int ans = uc[v];
vector<int> minsu(n+1, INF);
vector<int> mintu(n+1, INF);
vector<int> minsv(n+1, INF);
vector<int> mintv(n+1, INF);
vector<int> sc(n+1, INF);
vector<int> tc(n+1, INF);
sc[s] = 0;
tc[t] = 0;
minsu[s] = uc[s];
minsv[s] = vc[s];
mintu[t] = uc[t];
mintv[t] = vc[t];
pq.push({0, s});
while(not pq.empty())
{
int i = pq.top().second;
int c = pq.top().first;
pq.pop();
if(c>sc[i]) continue;
for(auto j: adjlist[i])
{
int cd = c + j.second;
if(cd==sc[j.first])
{
minsu[j.first] = min(minsu[i], minsu[j.first]);
minsv[j.first] = min(minsv[i], minsv[j.first]);
continue;
}
if(cd>sc[j.first]) continue;
minsu[j.first] = min(minsu[i], uc[j.first]);
minsv[j.first] = min(minsv[i], vc[j.first]);
sc[j.first] = cd;
pq.push({sc[j.first], j.first});
}
}
int st = sc[t];
pq.push({0, t});
vector<bool> visited(n+1, false);
while(not pq.empty())
{
int i = pq.top().second;
int c = pq.top().first;
visited[i] = true;
pq.pop();
if(c>tc[i]) continue;
for(auto j: adjlist[i])
{
int cd = c + j.second;
if(visited[j.first])
{
int x = sc[i] + tc[j.first] + j.second;
int y = sc[j.first] + tc[i] + j.second;
if(x==st || y==st)
{
if(sc[i]<sc[j.first])
{
x = minsu[i] + mintv[j.first];
y = minsv[i] + mintu[j.first];
ans = min({ans, x, y});
continue;
}
else
{
x = mintu[i] + minsv[j.first];
y = mintv[i] + minsu[j.first];
ans = min({ans, x, y});
continue;
}
}
}
if(cd==tc[j.first])
{
mintu[j.first] = min(mintu[i], mintu[j.first]);
mintv[j.first] = min(mintv[i], mintv[j.first]);
continue;
}
if(cd>tc[j.first]) continue;
mintu[j.first] = min(mintu[i], uc[j.first]);
mintv[j.first] = min(mintv[i], vc[j.first]);
tc[j.first] = cd;
pq.push({tc[j.first], j.first});
}
}
cout<<ans;
}
signed main()
{
fast_io;
int t=1;
//cin>>t;
while(t--)
{
solve();
}
cout<<endl;
}
# | 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... |