Submission #894759

#	Time	Username	Problem	Language	Result	Execution time	Memory
894759		asdasdqwer	Robot (JOI21_ho_t4)	C++14	24 / 100	277 ms	45120 KiB

Main

#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 (stderr)

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
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42