이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pli pair<long long,int>
#define iii pair<int,pii>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<pii>
#define pb(i) push_back(i)
#define all(x) x.begin(),x.end()
#define TEXT "a"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll inf = 1e15 + 5;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;
vector<pii> a[N];
vector<int> b[N], c[N];
vector<ll> dS, dT, dX, dY;
ll f[N], g[N];
int n,m;
int s,t,x,y;
void dijkstra(int s, vector<ll>& d){
d.resize(n + 5,inf);
priority_queue<pli,vector<pli>,greater<pli>> pq;
d[s] = 0;
pq.push(pli(0,s));
while(!pq.empty()){
int u = pq.top().se;
ll dis = pq.top().fi;
pq.pop();
if (dis > d[u]) continue;
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i].fi;
int w = a[u][i].se;
if (d[u] + w < d[v]){
d[v] = d[u] + w;
pq.push(pli(d[v],v));
}
}
}
}
void buildGraph(){
for (int u = 1; u <= n; u++){
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i].fi;
int w = a[u][i].se;
if (dS[v] == dS[u] + w && dS[t] == dS[u] + w + dT[v]){
b[u].push_back(v);
c[v].push_back(u);
//cout << u << " " << v << " " << w << "\n";
}
}
}
}
void cal(int u){
if (f[u] != inf) return;
f[u] = dX[u];
g[u] = dY[u];
for (int v : c[u]){
cal(v);
f[u] = min(f[u], f[v]);
g[u] = min(g[u], g[v]);
}
}
void calR(int u){
if (f[u] != inf) return;
f[u] = dX[u];
g[u] = dY[u];
for (int v : b[u]){
calR(v);
f[u] = min(f[u], f[v]);
g[u] = min(g[u], g[v]);
}
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
if (fopen(TEXT".inp","r")){
freopen(TEXT".inp","r",stdin);
freopen(TEXT".out","w",stdout);
}
cin >> n >> m;
cin >> s >> t >> x >> y;
for (int i = 1; i <= m; i++){
int u,v,w;
cin >> u >> v >> w;
a[u].pb(pii(v,w));
a[v].pb(pii(u,w));
}
dijkstra(s, dS);
dijkstra(t, dT);
buildGraph();
swap(x,y);
dijkstra(x, dX);
dijkstra(y, dY);
for (int i = 1; i <= n; i++) f[i] = g[i] = inf;
cal(t);
ll res = dX[y];
for (int i = 1; i <= n; i++){
res = min(res, f[i] + g[i]);
}
for (int i = 1; i <= n; i++) f[i] = g[i] = inf;
calR(s);
for (int i = 1; i <= n; i++){
res = min(res, f[i] + g[i]);
}
cout << res << "\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < a[u].size(); i++){
| ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void buildGraph()':
commuter_pass.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < a[u].size(); i++){
| ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen(TEXT".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(TEXT".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... |