Submission #638065

#	Time	Username	Problem	Language	Result	Execution time	Memory
638065		chjiao	Robot (JOI21_ho_t4)	C++17	100 / 100	781 ms	85088 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int MN = 1e5+1;// 1e5;
vector<ll> dp(MN, MAX);
vector<map<int,ll>> dp2(MN);
vector<map<int,ll>> colorsum(MN);  //elemnent, color, sum 
vector<map<int,vector<pair<int,ll>>>> neighbors(MN); //element, map<bridge color> , element, bridge lenghth
struct quadriple{
    ll value;
    int curr;
    //bool changed;
    int roadcolor;
    // int roadvalue;
};
struct cmp {
    bool operator ()(quadriple & a, quadriple& b){
        return a.value > b.value;
    }
};
void dijkstra(int s) {
    priority_queue<quadriple, vector<quadriple>, cmp> pq;
    dp[0] = 0;
    pq.push({0,0,0});

    while(!pq.empty()){
        quadriple c = pq.top();
        pq.pop();
        //case 1, if color changed

        if(c.roadcolor!= 0){
            if(dp2[c.curr][c.roadcolor] == c.value){
                for(auto [element, value]: neighbors[c.curr][c.roadcolor]){
                    ll case1 = colorsum[c.curr][c.roadcolor] -value+c.value;
                    if(dp[element] > case1){
                        dp[element] = case1;
                        pq.push({case1, element, 0});
                    }
                }
            }
            

        }else if(dp[c.curr] == c.value){        //cases 2, if color hasn't changed
            for(auto &[color,v]: neighbors[c.curr]){
                for(auto &[element, value]: v){
                    //cases 2.1 change myself
                    ll newcase = c.value +value;
                    if(newcase<dp[element]){
                        dp[element] = newcase;
                        pq.push({newcase, element, 0});
                    }
                
                    //cases 2.2 change other
                    newcase =  colorsum[c.curr][color]+ c.value- value;
                    if(newcase< dp[element]){
                        dp[element] = newcase;
                        pq.push({newcase, element , 0});
                    }

                    //cases 2.3 When changing i, affects i+2
                    newcase = c.value;
                    if(!dp2[element].count(color) ||dp2[element][color] > newcase ){
                        dp2[element][color] = newcase;
                        pq.push({newcase, element, color});
                    }
                }


                        
            }
        }
        
        //cases 2, if color hasn't changed
        //cases 2.1 change myself
        //cases 2.2 change other
        //cases 2.3 When changing i, affects i+2
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("Robot.in", "r", stdin);
    //freopen("nocross.out", "w", stdout); 
    int N,M,a,b,c,d;
    cin >> N >> M;
    
    for(int i=0; i<M; i++){
        cin >> a >> b >> c >> d;
        a--;
        b--;
        neighbors[a][c].push_back(make_pair(b,d));
        neighbors[b][c].push_back(make_pair(a,d));
        colorsum[a][c] +=d;
        colorsum[b][c] +=d;

    }

    dijkstra(0);
    if(dp[N-1] == MAX){
        cout << -1 << endl;
        return 0;
    }
    cout << dp[N-1] << endl;
}

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