이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
#define int ll
int mod = 1e9+7;
// int inf = 1e18;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// ifstream cin ("shortcut.in");
// ofstream cout ("shortcut.out");
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
--s; --t; --u; --v;
vector<pair<int,int>> adj[n];
for(int i = 0; i < m; ++i){
int a,b,c;
cin >> a >> b >> c;
--a; --b;
adj[a].push_back({c,b});
adj[b].push_back({c,a});
}
vector<int> dis(n, 1e18);
dis[s] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<set<int>> par(n);
pq.push({0, s});
while(!pq.empty()){
pair<int,int> a = pq.top(); pq.pop();
if(dis[a.ss]!=a.ff){
continue;
}
for(auto &[w, nxt] : adj[a.ss]){
if(a.ff+w<dis[nxt]){
if(par[nxt].size()) par[nxt].clear();
par[nxt].insert(a.ss);
pq.push({a.ff+w, nxt});
dis[nxt] = a.ff+w;
}else if(a.ff+w==dis[nxt]){
par[nxt].insert(a.ss);
}
}
}
vector<bool> ways(n, false);
vector<bool> check(n, false);
queue<int> q;
q.push({t});
check[t] = true;
while(!q.empty()){
int a = q.front(); q.pop();
ways[a] = true;
for(int i : par[a]){
if(!check[i]){
q.push(i);
check[i] = true;
}
}
}
vector<int> how_many(n , 0);
for(int i = 0; i < n; ++i){
if(ways[i]){
for(int j : par[i]){
how_many[j]++;
}
}
}
using te = pair<int,pair<int,pair<bool,int>>>;
priority_queue<te, vector<te>, greater<te>> ppq;
ppq.push({0,{u,{0,0}}});
dis.assign(n, 1e18);
dis[u] = 0;
while(!ppq.empty()){
int weight = ppq.top().ff;
int node = ppq.top().ss.ff;
bool go = ppq.top().ss.ss.ff;
int only_forward = ppq.top().ss.ss.ss;
ppq.pop();
if(dis[node]!=weight){
continue;
}
// i should remember how i got to node as a child -> can go only to parent 2
// as a parent can go only go to children 1
// 1 if i am not parent of the next node skip
// 2 if the next node isnt my parent skip
for(auto &[w, nxt] : adj[node]){
if(!go&&ways[node]&&ways[nxt]&&weight<dis[nxt]){
if((only_forward==1&&par[nxt].count(node)==0)||(only_forward==2&&par[node].count(nxt)==0)){
//nothing just didn't want everything to negate
}else{
dis[nxt] = weight;
ppq.push({weight,{nxt,{nxt==s||nxt==t, par[node].count(nxt)==0?1:2}}});
}
}
if(weight+w<dis[nxt]){
dis[nxt] = weight+w;
ppq.push({weight+w,{nxt,{go,only_forward}}});
}
}
}
cout << dis[v] << '\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... |