이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N=100'010;
vector<array<long long, 2>> g[N];
int n, m;
vector<long long> dist(int s) {
priority_queue<pair<long long, long long>> pq;
vector<bool> vis(n);
vector<long long> d(n,1e18);
pq.push({0,s});
d[s]=0;
while(pq.size()) {
int at=pq.top().second;
pq.pop();
if(vis[at])continue;
vis[at]=1;
for(auto to:g[at]) {
if(d[to[0]]>d[at]+to[1]) {
d[to[0]]=d[at]+to[1];
pq.push({-d[to[0]],to[0]});
}
}
}
return d;
}
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int S, T, U, V;
cin >> S >> T >> U >> V;
S--,T--,U--,V--;
for(int i = 0;i<m;i++) {
long long a, b, c;
cin >> a >> b >> c;
a--,b--;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
vector<long long> s=dist(S), t=dist(T), u=dist(U), v=dist(V);
long long dpu[n], dpv[n];
dpu[0]=dpv[0]=1e18;
vector<pair<long long, int>> is;
for(int i = 0;i<n;i++) {
dpu[i]=dpv[i]=1e18;
if(s[i]+t[i]==s[T]){
is.push_back({s[i],i});
}
}
sort(is.begin(), is.end());
long long res=1e18;
for(auto [asdf,i]:is) {
dpu[i]=u[i];
dpv[i]=v[i];
for(auto to:g[i]) {
if(t[i]+to[1]+s[to[0]]==s[T]) {
dpu[i]=min(dpu[i],dpu[to[0]]);
dpv[i]=min(dpv[i],dpv[to[0]]);
}
}
res=min(res,dpu[i]+v[i]);
res=min(res,u[i]+dpv[i]);
}
res=min(res,u[V]);
cout << res << endl;
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... |