이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct xy { long long x, y, z, ck, idx; };
vector<xy>edge[212], redge[212];
long long n, m, dist[4][212], bef[4][212], rdist[4][212], u[51515], v[51515], c[51515];
void dijkstra(long long st, long long flag, long long dist[4][212], vector<xy> edge[212]) {
for (int i = 1; i <= n; i++)dist[flag][i] = 1e15;
dist[flag][st] = 0;
priority_queue<pair<long long , long long >>H;
H.push({0, st});
while (!H.empty()) {
auto g = H.top(); H.pop();
long long now = g.second;
if (dist[flag][now] != -g.first)continue;
for (xy E : edge[now]) {
if (E.ck)continue;
long long nxt = E.x, c = E.y;
if (dist[flag][nxt] > dist[flag][now] + c) {
dist[flag][nxt] = dist[flag][now] + c;
H.push({ -dist[flag][nxt],nxt });
}
}
}
}
int main() {
long long i, j; scanf("%lld%lld", &n, &m);
for (i = 0; i < m; i++) {
long long d; scanf("%lld%lld%lld%lld", &u[i], &v[i], &c[i], &d);
edge[u[i]].push_back({ v[i],c[i],d,0,i });
redge[v[i]].push_back({ u[i],c[i],d,0,i });
}
dijkstra(1, 0, dist, edge); dijkstra(n, 1, dist, edge);
dijkstra(1, 0, rdist, redge); dijkstra(n, 1, rdist, redge);
for (long long tc = 0; tc < 2; tc++) {
for (i = 0; i < m; i++) {
if (dist[tc][u[i]] + c[i] == dist[tc][v[i]]) {
bef[tc][v[i]] = i;
}
}
}
long long ans = dist[0][n] + dist[1][1];
for (i = 1; i <= n; i++) {
for (j = 0; j < edge[i].size(); j++) {
long long u = i, v = edge[i][j].x, c = edge[i][j].y, d = edge[i][j].z, idx = edge[i][j].idx;
if (bef[0][v] != idx && bef[1][v] != idx) {
ans = min(ans, dist[0][v] + c + rdist[1][u] + dist[1][1] + d);
ans = min(ans, dist[1][v] + c + rdist[0][u] + dist[0][n] + d);
ans = min(ans, dist[0][v] + c + rdist[1][u] + dist[1][v] + c + rdist[0][u] + d);
}
else {
edge[i][j].ck = 1;
edge[v].push_back({ u, c, d });
dijkstra(1, 2, dist, edge);
dijkstra(n, 3, dist, edge);
ans = min(ans, dist[2][n] + dist[3][1] + d);
edge[v].pop_back();
edge[i][j].ck = 0;
}
}
}
if (ans > 1e15)printf("-1");
else printf("%lld\n", ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edge[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
ho_t4.cpp:29:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
long long i, j; scanf("%lld%lld", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:31:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
long long d; scanf("%lld%lld%lld%lld", &u[i], &v[i], &c[i], &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |