oj.uz

답안 #955378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955378 2024-03-30T10:06:56 Z blackslex Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 147 ms 16576 KB 
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int n, m, s, t, cs, ct, x, y, z;

int main() {
    scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &cs, &ct);
    vector<vector<pii>> v(n + 5, vector<pii>());
    while (m--) scanf("%d %d %d", &x, &y, &z), v[x].emplace_back(y, z), v[y].emplace_back(x, z);
    vector<int> d(n + 5, 1e9), par(n + 5);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.emplace(d[s] = 0, s);
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        for (auto &[tn, td]: v[nn]) if (d[tn] > d[nn] + td) par[tn] = nn, pq.emplace(d[tn] = d[nn] + td, tn);
    }
    vector<int> u{t};
    while (par[u.back()]) u.emplace_back(par[u.back()]);
    for (auto &e: u) v[n + 1].emplace_back(e, 0), v[e].emplace_back(n + 1, 0);
    vector<int> d2(n + 5, 1e9);
    pq.emplace(d2[cs] = 0, cs);
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        for (auto &[tn, td]: v[nn]) if (d2[tn] > d2[nn] + td) pq.emplace(d2[tn] = d2[nn] + td, tn);
    }
    printf("%d", d2[ct]);
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &cs, &ct);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:11:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     while (m--) scanf("%d %d %d", &x, &y, &z), v[x].emplace_back(y, z), v[y].emplace_back(x, z);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 14796 KB Output is correct
2 Correct 119 ms 14292 KB Output is correct
3 Correct 118 ms 16576 KB Output is correct
4 Incorrect 113 ms 14648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 15048 KB Output is correct
2 Correct 140 ms 14852 KB Output is correct
3 Correct 130 ms 15308 KB Output is correct
4 Correct 146 ms 14792 KB Output is correct
5 Correct 132 ms 15304 KB Output is correct
6 Correct 119 ms 15936 KB Output is correct
7 Correct 136 ms 16236 KB Output is correct
8 Correct 135 ms 14800 KB Output is correct
9 Correct 130 ms 15308 KB Output is correct
10 Correct 147 ms 14880 KB Output is correct
11 Incorrect 55 ms 8968 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 14796 KB Output is correct
2 Correct 119 ms 14292 KB Output is correct
3 Correct 118 ms 16576 KB Output is correct
4 Incorrect 113 ms 14648 KB Output isn't correct
5 Halted 0 ms 0 KB -