Submission #1146601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146601		antistrangequark	Robot (JOI21_ho_t4)	C++20	0 / 100	101 ms	13248 KiB

Main

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

int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m;
    cin >> n >> m;
    vector<vector<pair<long long, long long>>> g(n);
    long long c[m];
    long long p[m];
    vector<unordered_map<long long, long long>> v(n);
    for(int i = 0; i < m; i++){
        long long a, b;
        cin >> a >> b >> c[i] >> p[i];
        a--;
        b--;
        g[a].push_back(make_pair(b, i));
        g[b].push_back(make_pair(a, i));
        unordered_map<long long, long long> map = v[a];
        map[c[i]] = map[c[i]] + p[i];
        v[a] = map;
        map = v[b];
        map[c[i]] = map[c[i]] + p[i];
        v[b] = map;
    }
    vector<long long> dist(n, LLONG_MAX/4);
    vector<int> pr(n, 0);
	using T = pair<long long, long long>;
	priority_queue<T, vector<T>, greater<T>> q;
    dist[0] = 0;
    q.push({0, 0});
    while(!q.empty()){
        auto a = q.top();
        q.pop();
        if(pr[a.first] == 1){
            continue;
        }
        else{
            for(auto z: g[a.first]){
                unordered_map<long long, long long> curr = v[a.first];
                long long w = min(p[z.second], curr[c[z.second]] - p[z.second]);
                if(dist[a.first] + w < dist[z.first]){
                    dist[z.first] = dist[a.first] + w;
                    q.push({z.first, dist[z.first]});
                }
            }
        }
        pr[a.first] = 1;
    }
    if(dist[n-1] != LLONG_MAX/4){
        for(int i = 0; i < n; i++){
            cout << dist[i] << " ";
        }
        cout << endl << endl << dist[n-1];
    }
    else{
        cout << -1;
    }
}

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