Submission #1109943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109943		kfhjad	Robot (JOI21_ho_t4)	C++17	100 / 100	198 ms	42748 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<array<int, 3>> adj[100005];
ll cost[100005];
bool visited[100005];
unordered_map<int, array<ll, 2>> s[100005]; // didnt change road, changed road

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    
    for (int i = 1; i <= N; ++i)
        cost[i] = LLONG_MAX;
    
    for (int i = 0; i < M; ++i)
    {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        
        adj[a].push_back({b, c, p});
        adj[b].push_back({a, c, p});
    }
    
    using T = array<ll, 2>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({0, 1});
    
    while (!pq.empty())
    {
        auto [curcost, node] = pq.top();
        pq.pop();
        
        if (visited[node])
            continue;
        
        visited[node] = true;
        
        unordered_map<int, array<ll, 2>> m; // sum, best option
        
        for (auto& [i, c, p] : adj[node])
            m[c][1] = curcost;
        
        for (auto& [i, c, p] : adj[node])
        {
            m[c][0] += p;
            
            if (visited[i])
                m[c][1] = min(m[c][1], s[i][node][1] - p);
        }
        
        for (auto& [i, c, p] : adj[node])
        {
            if (visited[i])
                continue;
            
            s[node][i][0] = m[c][1] + m[c][0] - p;
            s[node][i][1] = curcost + p;
            
            ll next = min(s[node][i][0], s[node][i][1]);
            
            if (next < cost[i])
                pq.push({cost[i] = next, i});
        }
    }
    
    cout << (cost[N] == LLONG_MAX ? -1 : cost[N]) << endl;
    
    return 0;
}

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