Submission #1139558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139558		trMatherz	Robot (JOI21_ho_t4)	C++20	0 / 100	317 ms	43224 KiB

Main

#include <iostream> 

 
// #include <fstream>
// std::ifstream cin ("hopscotch.in");
// std::ofstream cout ("hopscotch.out");
 
 
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <iterator>
#include <complex>
 

using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define f first
#define s second
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
typedef uint64_t hash_t;
ll const inf = (ll) 1e15 + 7; 
int const M = (ll) 1e9 + 7; 
int const IM = (ll) 5e8 + 4; 


struct stuff {
    ll x, y, z; 
}; 
auto cmp = [](auto x, auto y) { return x.z > y.z; };
int main() {
    int n, m; cin >> n >> m; 
    vector<map<int, vector<stuff>>> a(n); 
    vector<map<int, ll>> b(n); 
    for(int i = 0; i < m; i++) {
        ll x, y, z, p; cin >> x >> y >> z >> p; 
        x--, y--; 
        if(!a[x].count(0)) a[x][0] = vector<stuff>(), b[x][0] = 0; 
        if(!a[x].count(z)) a[x][z] = vector<stuff>(), b[x][z] = 0; 
        if(!a[y].count(0)) a[y][0] = vector<stuff>(), b[y][0] = 0; 
        if(!a[y].count(z)) a[y][z] = vector<stuff>(), b[y][z] = 0; 
        a[x][0].push_back({y, z, p});
        a[x][z].push_back({y, z, p});
        b[x][0] += p; 
        b[x][z] += p; 
        a[y][0].push_back({x, z, p});
        a[y][z].push_back({x, z, p});
        b[y][0] += p; 
        b[y][z] += p; 
    }
    vector<map<ll, ll>> dp(n); 
    priority_queue<stuff, vector<stuff>, decltype(cmp)> q(cmp); 
    q.push({0, 0, 0}); 
    while(!q.empty()) {
        auto u = q.top(); q.pop(); 
        if(dp[u.x].count(u.y) && dp[u.x][u.y] <= u.z) continue; 
        dp[u.x][u.y] = u.z; 
        for(auto &l : a[u.x][u.y]) {
            q.push({l.x, 0, u.z + b[u.x][u.y] - l.z}); 
            if(u.y == 0) {
                q.push({l.x, 0, u.z + l.z}); 
                q.push({l.x, l.y, u.z}); 
            }
        }
    }
    cout << (!dp[n - 1].count(0) ? -1 : dp[n - 1][0]); 
}       

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