이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long INF = 1e18;
const int N = 1e5 + 4;
int n, m;
int S, T;
int U, V;
long long d[N][4];
long long dp[N][2];
vector<pair<int, int>> adj[N];
void Dijkstra(int s, int type) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
while (pq.size()) {
long long du = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (du != d[u][type]) continue;
for (pair<int, int> x: adj[u]) {
int v = x.fi, w = x.se;
if (mini(d[v][type], du + w))
pq.push(make_pair(d[v][type], v));
}
}
}
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, w; cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
Dijkstra(S, 0); Dijkstra(T, 1);
Dijkstra(U, 2); Dijkstra(V, 3);
for (int i = 1; i <= n; i++)
dp[i][0] = dp[i][1] = INF;
// calc array dp[_][__]
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 1; i <= n; i++) {
if (d[i][0] + d[i][1] == d[T][0])
pq.push(make_pair(d[i][0], i));
}
while (pq.size()) {
long long du = pq.top().fi;
int u = pq.top().se;
pq.pop();
mini(dp[u][0], d[u][2]);
mini(dp[u][1], d[u][3]);
for (pair<int, int> x: adj[u]) {
int v = x.fi, w = x.se;
if (du + w + d[v][1] == d[T][0]) {
mini(dp[v][0], dp[u][0]);
mini(dp[v][1], dp[u][1]);
}
}
}
long long ans = d[V][2];
for (int i = 1; i <= n; i++) {
if (d[i][0] + d[i][1] == d[T][0]) {
mini(ans, dp[i][0] + d[i][3]);
mini(ans, dp[i][1] + d[i][2]);
}
}
cout << ans;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void Dijkstra(int, int)':
commuter_pass.cpp:27:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
27 | for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
| ^~~
commuter_pass.cpp:27:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
27 | for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
| ^~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main() {
| ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | 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... |