제출 #1251137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251137		dyogorb	Robot (JOI21_ho_t4)	C++20	100 / 100	912 ms	82312 KiB

Main

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

#define darvem ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl '\n'
#define ll long long
#define int long long

signed main(){
    darvem;

    int n, m;
    cin >> n >> m;

    vector<map<int, vector<pair<int, int>>>> g(n);
    vector<map<int, int>> psum(n);
    for(int i = 0; i < m; i++){
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--;b--;
        g[a][c].push_back({b, p});
        g[b][c].push_back({a, p});        
        psum[a][c] += p;
        psum[b][c] += p;
    }

    vector<int> dp(n, -1);
    dp[0] = 0;
    vector<map<int, int>> dp2(n);

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push({0, 0, 0});

    vector<int> dst(n, -1);
    while(!pq.empty()){
        auto [d, v, pc] = pq.top(); pq.pop();        

        if(pc){
            if(dp2[v][pc] != d) continue;

            for(auto [u, w] : g[v][pc]){
                int cost = psum[v][pc] - w;
                if(dp[u] == -1 or dp[u] > cost + d){
                    dp[u] = cost + d;
                    pq.push({d + cost, u, 0});
                }
            }
        } else{
            if(dp[v] != d) continue;
            for (auto &[c, e] : g[v])
            {
                for (auto [u, w] : e)
                {
                    // caso 1, vou trocar de cor agora e depois outra cor será trocada
                    if(dp[u] == -1 or dp[u] > d + w){
                        dp[u] = d + w;
                        pq.push({dp[u], u, 0});
                    }

                    // caso 2, não troco de cor
                    if(dp[u] == -1 or dp[u] > d + psum[v][c] - w){
                        dp[u] = d + psum[v][c] - w;
                        pq.push({dp[u], u, 0});
                    }

                    // caso 3, vou trocar de cor, mas não agora e sim no proximo
                    if(!dp2[u].count(c) or dp2[u][c] > d){
                        dp2[u][c] = d;
                        pq.push({d, u, c});
                    }
                }
                
            }
            
        }    
    }
    
    cout << dp.back() << endl;
}

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