oj.uz

답안 #894759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894759 2023-12-28T22:29:13 Z asdasdqwer Robot (JOI21_ho_t4) C++14
24 / 100
 277 ms 45120 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii array<int,3>
#define pi array<int,2>

signed main() {
    int n,m;cin>>n>>m;
    vector<vector<pii>> g(n);
    for (int i=0;i<m;i++) {
        int a,b,c,p;cin>>a>>b>>c>>p;a--;b--;
        g[a].push_back({c, b, p});
        g[b].push_back({c, a, p});
    }

    for (int i=0;i<n;i++) {
        sort(g[i].begin(), g[i].end());
    }

    vector<vector<pi>> gg(n);

    for (int i=0;i<n;i++) {
        vector<vector<pii>> buckets;
        for (auto x:g[i]) {
            if (buckets.size() == 0) {
                buckets.push_back({x});
            }

            else if (buckets.back().back()[0] == x[0]) {
                buckets[buckets.size()-1].push_back(x);
            }

            else {
                buckets.push_back({x});
            }
        }

        for (auto &x:buckets) {
            if (x.size() == 1) {
                gg[i].push_back({x[0][1], 0});
            }

            else if (x.size() == 2) {
                auto y1 = x[0], y2 = x[1];
                int mn = min(y1[2], y2[2]);
                gg[y1[1]].push_back({y2[1], mn});
                gg[y2[1]].push_back({y1[1], mn});
            }

            if (x.size() != 1) {
                for (auto &y:x) {
                    gg[i].push_back({y[1], y[2]});
                }
            }
        }
    }

    vector<int> dis(n, 1e15);
    priority_queue<pi> pq;
    dis[0] = 0;

    for (int i=0;i<n;i++) {
        pq.push({-dis[i], i});
    }

    vector<bool> vis(n, false);

    while (!pq.empty()) {
        auto [cost, node]=pq.top();pq.pop();
        if (vis[node])continue;
        vis[node] = true;

        for (auto [ne, we]:gg[node]) {
            if (dis[ne] > dis[node] + we) {
                dis[ne] = dis[node] + we;
                pq.push({-dis[ne], ne});
            }
        }
    }

    if (dis.back() == (int)1e15) {
        cout<<-1<<"\n";
        return 0;
    }

    cout<<dis.back()<<"\n";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |         auto [cost, node]=pq.top();pq.pop();
      |              ^
Main.cpp:74:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |         for (auto [ne, we]:gg[node]) {
      |                   ^

Subtask #1
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 13000 KB Output is correct
2 Correct 43 ms 6352 KB Output is correct
3 Correct 134 ms 18216 KB Output is correct
4 Correct 60 ms 9684 KB Output is correct
5 Correct 263 ms 41204 KB Output is correct
6 Correct 265 ms 45120 KB Output is correct
7 Correct 236 ms 39684 KB Output is correct
8 Correct 256 ms 35876 KB Output is correct
9 Correct 277 ms 36036 KB Output is correct
10 Correct 153 ms 23768 KB Output is correct
11 Correct 113 ms 20940 KB Output is correct

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -