이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int nd = 1e5 + 5 , INF = 1e18;
vector<pair<int,int> > adj[nd];
vector<int> dis[4] , g[nd + 4] , in(nd + 5 , 0) , topo , f(nd + 4 , INF) , par[nd + 4];
priority_queue< pair<int , int> , vector< pair<int,int> > , greater< pair<int,int> > >q;
bool vs[nd + 4];
void dijs(int r , int p){
q.push({0 , r});
dis[p][r] = 0;
memset(vs , false , nd);
while(!q.empty()){
int u = q.top().second , h = q.top().first;
q.pop();
if(vs[u])continue;
//cout << r << " " << h << " " << u <<" " << '\n';
vs[u] = true;
for(auto v : adj[u])if(!vs[v.first]){
//cout << v.first << '\n';
if(h + v.second < dis[p][v.first]){
dis[p][v.first] = h + v.second , q.push({dis[p][v.first] , v.first});
}
}
}
}
void build(int u){
for(auto [v, vw] : adj[u]){
if(dis[0][u] == dis[0][v] + vw){
g[v].push_back(u);
par[u].push_back(v);
++in[u];
build(v);
}
}
}
void bfs(int s){
queue<int> h;
h.push(s);
while(!h.empty()){
int u = h.front();
h.pop();
topo.push_back(u);
for(int v : g[u]){
--in[v];
if(!in[v])h.push(v);
}
}
}
void solve(){
int n,m;
int s ,t , x, y;
cin >> n >> m;
cin >> s >> t >> x >> y;
for(int i = 0;i < 4; ++i)dis[i].resize(nd , INF);
for(int i = 1;i <= m; ++i){
int l , r ,w;
cin >> l >> r >> w;
adj[l].push_back({r , w}) , adj[r].push_back({l , w});
}
dijs(s , 0) , dijs(t , 1) , dijs(x , 2) , dijs(y , 3);
memset(vs , false , sizeof(vs));
build(t);bfs(s);
//for(int i = 1;i <= n; ++i)cout << in[i] << '\n';
f[s] = dis[2][s];
int res = INF;
for(int i = 1;i < topo.size(); ++i){
int u = topo[i];
f[u] = dis[2][u];
for(auto v : par[u]){
f[u] = min(f[u] , f[v]);
}
res = min(res , f[u] + dis[3][u]);
}
f[s] = dis[3][s];
res = min(res ,f[s] + dis[2][s]);
for(int i = 1;i < topo.size(); ++i){
int u = topo[i];
f[u] = dis[3][u];
for(auto v : par[u]){
f[u] = min(f[u] , f[v]);
}
res = min(res , f[u] + dis[2][u]);
}
res = min(res , dis[2][y]);
cout << res;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
#define task "task"
//freopen(task".inp","r",stdin);freopen(task".out","w",stdout);
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void build(long long int)':
commuter_pass.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for(auto [v, vw] : adj[u]){
| ^
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:80:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 1;i < topo.size(); ++i){
| ~~^~~~~~~~~~~~~
commuter_pass.cpp:92:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 1;i < topo.size(); ++i){
| ~~^~~~~~~~~~~~~
# | 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... |