이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
#define Task "bus"
using namespace std;
const int N = 1e5 + 5;
vector<int> ds , dt , du , dv;
int n , m , u , v , s , t , ok[N];
int res;
vector<pair<int , int>> g[N];
void dijkstra(int u , vector<int> &d){
d . resize(n + 1);
for(int i = 1 ; i <= n ; i++) d[i] = 1e18;
d[u] = 0;
priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
pq . push({d[u] , u});
while(pq . size()){
int u = pq . top() . second;
int du = pq . top() . first;
pq . pop();
if(d[u] != du) continue;
for(pair<int , int> nex : g[u]){
if(d[nex . first] > d[u] + nex . second){
d[nex . first] = d[u] + nex . second;
pq . push({d[nex . first] , nex . first});
}
}
}
}
void Get(int s , int t){
vector<int> dp[2] , ds;
dp[0] . resize(n + 1);
dp[1] . resize(n + 1);
ds . resize(n + 1);
for(int i = 0 ; i <= n ; i++) ds[i] = 1e18 , dp[0][i] = 1e18 , dp[1][i] = 1e18;
ds[s] = 0;
memset(ok , false , sizeof(ok));
priority_queue<pair<int , pair<int , int>> , vector<pair<int , pair<int , int>>> , greater<pair<int , pair<int , int>>>> pq;
pq . push({0 , {s , 0}});
while(pq . size()){
int u , par;
int c = pq . top() . first;
u = pq . top() . second . first;
par = pq . top() . second . second;
pq . pop();
if(!ok[u]){
dp[0][u] = min(dp[0][par] , du[u]);
dp[1][u] = min(dp[1][par] , dv[u]);
ok[u] = true;
for(pair<int , int> nex : g[u]){
if(ds[nex . first] >= ds[u] + nex . second){
ds[nex . first] = ds[u] + nex . second;
pq . push({ds[nex . first] , {nex . first , u}});
}
}
}
else if(c == ds[u] && min(dp[0][par] , du[u]) + min(dp[1][par] , dv[u]) <= dp[0][u] + dp[1][u]){
dp[0][u] = min(dp[0][par] , du[u]);
dp[1][u] = min(dp[1][par] , dv[u]);
}
}
res = min(res , dp[0][t] + dp[1][t]);
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen(Task".inp","r")){
freopen(Task".inp","r",stdin);
freopen(Task".out","w",stdout);
}
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
for(int i = 1 ; i <= m ; i++){
int u , v , c;
cin >> u >> v >> c;
g[u] . push_back({v , c});
g[v] . push_back({u , c});
}
dijkstra(u , du);
dijkstra(v , dv);
res = du[v];
Get(s , t);
Get(t , s);
cout << res;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:78:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(Task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen(Task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |