Submission #529558

#	Time	Username	Problem	Language	Result	Execution time	Memory
529558		syl123456	Robot (JOI21_ho_t4)	C++17	100 / 100	1877 ms	88768 KiB

Main

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<ll, int> pl;

struct edge {
    int u, v, c, p;
    edge(int _u, int _v, int _c, int _p) : u(_u), v(_v), c(_c), p(_p) {}
    int go(int i) {
        return u ^ v ^ i;
    }
};

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<edge> e;
    map<pi, ll> mp;
    map<pi, int> id;
    for (int i = 0; i < m; ++i) {
        int x, y, z, w;
        cin >> x >> y >> z >> w;
        --x, --y;
        g[x].push_back(e.size()), g[y].push_back(e.size());
        if (!id.count({x, z}))
            id[{x, z}] = g.size(), g.emplace_back();
        g[id[{x, z}]].push_back(e.size());
        if (!id.count({y, z}))
            id[{y, z}] = g.size(), g.emplace_back();
        g[id[{y, z}]].push_back(e.size());
        e.emplace_back(x, y, z, w);
        mp[{x, z}] += w, mp[{y, z}] += w;
    }
    vector<int> v(g.size());
    for (auto [i, j] : id)
        v[j] = i.first;
    vector<ll> dis(g.size(), INF);
    priority_queue<pl, vector<pl>, greater<pl>> pq;
    pq.emplace(0, 0);
    while (!pq.empty()) {
        int i;
        ll x;
        tie(x, i) = pq.top();
        pq.pop();
        if (dis[i] < INF)
            continue;
        dis[i] = x;
        if (i < n) {
            for (int ei : g[i])
                pq.emplace(x + min(mp[{i, e[ei].c}] - e[ei].p, (ll)e[ei].p), e[ei].go(i));
            for (int ei : g[i])
                pq.emplace(x, id[{e[ei].go(i), e[ei].c}]);
        }
        else {
            int _i = i;
            i = v[_i];
            for (int ei : g[_i])
                pq.emplace(x + mp[{i, e[ei].c}] - e[ei].p, e[ei].go(i));
        }
    }
    cout << (dis[n - 1] < INF ? dis[n - 1] : -1);
}

Compilation message (stderr)

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42