이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector <pair <long long,long long> > g[100100];
vector <pair <long long,long long> > gg[100100];
long long dists[100100],distv[100100],distu[100100];
void dijkstra(long long dist[],long long s){
memset(dist,0x3f, sizeof (long long) * (n + 10));
dist[s] = 0;
priority_queue <pair <long long,long long> ,vector <pair <long long,long long> > ,greater <pair <long long,long long > > > q;
for (long long i = 1;i <= n; i++){
q.push({dist[i],i});
}
while (!q.empty()){
long long u = q.top().second;
long long val = q.top().first;
q.pop();
if (val != dist[u])continue;
for (auto tmp:g[u]){
long long v = tmp.first;
long long len = tmp.second;
if (dist[v] > dist[u] + len){
dist[v] = dist[u] + len;
q.push({dist[v],v});
}
}
}
}
bool in[100100];
long long dp[2][100100];
void dfs(long long u){
dp[0][u] = distu[u];
dp[1][u] = distv[u];
in[u] = 1;
for (auto v:g[u]){
if (dists[v.first] + v.second == dists[u]){
if (!in[v.first]){
dfs(v.first);
}
dp[0][u] = min(dp[0][u],dp[0][v.first]);
dp[1][u] = min(dp[1][u],dp[1][v.first]);
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m;
long long s,t,u,v;
cin>>s>>t>>u>>v;
for (long long i = 1;i <= m;i ++){
long long uu,vv,w;
cin>>uu>>vv>>w;
g[uu].push_back({vv,w});
g[vv].push_back({uu,w});
}
dijkstra(dists,s);
dijkstra(distu,u);
dijkstra(distv,v);
dfs(t);
long long ans = distu[v];
for (long long i = 1;i <= n;i ++){
if (in[i]){
ans = min(ans,dp[0][i] + distv[i]);
ans = min(ans,dp[1][i] + distu[i]);
}
}
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... |