Submission #689152

#	Time	Username	Problem	Language	Result	Execution time	Memory
689152		JooDdae	Robot (JOI21_ho_t4)	C++17	34 / 100	3082 ms	149232 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

int n, m, X[200200], Y[200200], c[200200], p[200200];
ll s[200200][2], d[100100][2][2];
vector<array<int, 2>> v[100100];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        cin >> X[i] >> Y[i] >> c[i] >> p[i];
        for(int j=0;j<2;j++) d[i][j][0] = d[i][j][1] = INF;
        v[X[i]].push_back({Y[i], i}), v[Y[i]].push_back({X[i], i});
    }

    for(int i=1;i<=n;i++) {
        sort(v[i].begin(), v[i].end(), [&](const array<int, 2> &a, const array<int, 2> &b) { return c[a[1]] < c[b[1]]; });

        for(int j=0;j<v[i].size();j++) {
            int k = j;
            ll sum = p[v[i][j][1]];
            while(k+1 < v[i].size() && c[v[i][j][1]] == c[v[i][k+1][1]]) sum += p[v[i][++k][1]];
            for(int l=j;l<=k;l++) s[v[i][l][1]][i == X[v[i][l][1]]] = sum;
            j = k;
        }
    }

    pq.push({0, 1, 0, 0});

    while(!pq.empty()) {
        auto [cost, u, id, type] = pq.top(); pq.pop();
        if(d[id][u == X[id]][type] < cost) continue;
        if(u == n) return cout << cost, 0;

        for(auto [x, y] : v[u]) {
            bool k = x == X[y];
            ll C1 = cost + s[y][!k] - p[y], C2 = cost + p[y];

            if((!type || c[id] != c[y]) && C1 < d[y][k][1]) d[y][k][1] = C1, pq.push({C1, x, y, 1});
            if(C2 < d[y][k][0]) d[y][k][0] = C2, pq.push({C2, x, y, 0});
        }

        // 변경된 색으로 들어와서 변경되기 전 색과 같은 간선의 색을 그대로 나가는 처리

        if(type == 1 || !id) continue;

        for(auto [x, y] : v[u]) if(y != id && c[id] == c[y]) {
            bool k = x == X[y];
            ll C = cost + s[y][!k] - p[y] - p[id];
            if(C < d[y][k][1]) d[y][k][1] = C, pq.push({C, x, y, 1});
        }
    }

    cout << -1;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int j=0;j<v[i].size();j++) {
      |                     ~^~~~~~~~~~~~
Main.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             while(k+1 < v[i].size() && c[v[i][j][1]] == c[v[i][k+1][1]]) sum += p[v[i][++k][1]];
      |                   ~~~~^~~~~~~~~~~~~

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