Submission #692512

#	Time	Username	Problem	Language	Result	Execution time	Memory
692512		prairie2022	Robot (JOI21_ho_t4)	C++14	100 / 100	214 ms	35692 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define inf 1ll<<62
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define pii pair<int, int>
#define C first 
#define nb second.first 
#define sum second.first
#define yen second.second 
#define sp <<' '<<
using namespace std;


signed main(){
    fastio
    int n, m, a, b, c, p;
    cin >> n >> m;
    bitset<100001> vst;
    vector<vector<pair<int, pii>>> e(n+1); //color, neighbor, cost
    vector<vector<pair<int, pii>>> s(n+1, vector<pair<int, pii>> (1, {0ll, {0ll, inf}}));
    auto it=s[0].begin();
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0ll, 1ll});
    // color, sum of cost, needed cost
    for(; m; m--){
        cin >> a >> b >> c >> p;
        e[a].push_back({c, {b, p}});
        e[b].push_back({c, {a, p}});
    }
    for(int i=1; i<=n; i++){
        if(e[i].empty()) continue;
        sort(e[i].begin(), e[i].end());
        c = 0;
        for(const auto &x: e[i]){
            if(x.C!=c){
                c = x.C;
                s[i].push_back({c, {0ll, inf}});
            }
            s[i].back().sum += x.yen;
        }
    }
    /*for(int i=1; i<=n; i++){
        cout << i << ":\n";
        for(const auto &x: e[i])
            cout << x.C sp x.nb sp x.yen << '\n'; 
    }
    for(int i=1; i<=n; i++){
        cout << i << ":\n";
        for(const auto &x: s[i])
            cout << x.C sp x.sum sp x.yen << '\n'; 
    }*/
    s[1][0].yen = 0;
    while(!pq.empty()){
        m = pq.top().second;
        pq.pop();
        if(m==n) break;
        if(vst[m]) continue;
        vst[m] = 1;
        c = 0; //index of s
        for(const auto &x: e[m]){
            if(x.C!=s[m][c].C) c++;
            if(vst[x.nb]) continue;
            p = min(s[m][0].yen+min(x.yen, s[m][c].sum-x.yen), s[m][c].yen-x.yen);
            //cout << m sp x.nb sp p;
            if(p<s[x.nb][0].yen){
                s[x.nb][0].yen = p;
                pq.push({p, x.nb});
            }
            it = lower_bound(s[x.nb].begin(), s[x.nb].end(), make_pair(s[m][c].C, make_pair(0ll, 0ll)));
            it->yen = min(s[m][0].yen+(it->sum), it->yen);
            //cout sp (it->C) sp (it->yen) sp (it->sum) << '\n';
        }
    }
    if(s[n][0].yen==inf) cout << "-1\n";
    else cout << s[n][0].yen << '\n';
    return 0;
}

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