Submission #773302

#	Time	Username	Problem	Language	Result	Execution time	Memory
773302		mcdx9524	Robot (JOI21_ho_t4)	C++17	0 / 100	3080 ms	27300 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <vector <pair <int, int> > > 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({b, c});
        g[b].push_back({a, c});
    }
    vector <vector <pair <int, int> > > cg(n);
    for (int i = 0; i < n; i++) {
        multiset <int> colors;
        vector <pair <int, int> > cols;
        for (auto [v, c] : g[i]) {
            colors.insert(c);
            cols.push_back({c, v});
        }
        for (auto [v, c] : g[i]) {
            if (colors.count(c) == 1) {
                cg[i].push_back({v, 0});
            } else {
                cg[i].push_back({v, 1});
            }
        }
        sort(cols.begin(), cols.end());
        for (int j = 1; j < (int) cols.size(); j++) {
            if (cols[j].first == cols[j - 1].first && colors.count(cols[j].first) == 2) {
                cg[cols[j - 1].second].push_back({cols[j].second, 1});
                cg[cols[j].second].push_back({cols[j - 1].second, 1});
            }
        }
    }
    vector <int> d(n, inf);
    deque <int> q;
    q.push_front(0);
    d[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto [to, c] : cg[v]) {
            if (d[to] > d[v] + c) {
                d[to] = d[v] + c;
                if (c == 0) {
                    q.push_front(to);
                } else {
                    q.push_back(to);
                }
            }
        }
    }
    cout << (d[n - 1] == inf ? -1 : d[n - 1]) << '\n';
    return 0;
}
	

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