oj.uz

답안 #955380

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

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

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<ll> d(n + 5, 1e18);
    vector<int> 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<ll> d2(n + 5, 1e18);
    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("%lld", d2[ct]);
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &cs, &ct);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:12:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     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 131 ms 16328 KB Output is correct
2 Correct 174 ms 16192 KB Output is correct
3 Correct 143 ms 20164 KB Output is correct
4 Incorrect 137 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 17448 KB Output is correct
2 Correct 152 ms 17608 KB Output is correct
3 Correct 151 ms 18632 KB Output is correct
4 Correct 147 ms 17604 KB Output is correct
5 Correct 186 ms 18112 KB Output is correct
6 Correct 140 ms 18732 KB Output is correct
7 Correct 155 ms 20232 KB Output is correct
8 Correct 208 ms 17612 KB Output is correct
9 Correct 158 ms 18124 KB Output is correct
10 Correct 195 ms 17460 KB Output is correct
11 Correct 64 ms 15044 KB Output is correct
12 Correct 145 ms 22940 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 16328 KB Output is correct
2 Correct 174 ms 16192 KB Output is correct
3 Correct 143 ms 20164 KB Output is correct
4 Incorrect 137 ms 16160 KB Output isn't correct
5 Halted 0 ms 0 KB -