Submission #637065

#	Time	Username	Problem	Language	Result	Execution time	Memory
637065		chjiao	Robot (JOI21_ho_t4)	C++17	0 / 100	461 ms	44596 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;// 1e5;
vector<map<int, pair<int,int>>> colorsum(1e5);
vector<vector<pair<int,pair<int,int>>>> neighbors(1e5);
vector<int> dp(MN, INT_MAX);
int visited[MN];
struct quadriple{
    int value;
    int curr;
    bool changed;
    int roadcolor;
    int roadvalue;
    quadriple(int _value, int _curr, bool _changed, int _roadcolor, int _roadvalue){
        value = _value;
        curr = _curr;
        changed = _changed;
        roadcolor = _roadcolor;
        roadvalue = _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;
    pq.push(quadriple(0,0,false,0,0));
    while (!pq.empty()) {
        quadriple c = pq.top(); 
        pq.pop();
        if(visited[c.curr] == false){
            visited[c.curr] = true;
            dp[c.curr] =c.value;
            for(auto& [pos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
                int color, num;
                tie(color, num) = x;
                if(colorsum[c.curr][color].second ==1){
                    pq.push(quadriple(c.value, pos, false, 0,0));
                }else{
                    if(c.changed == true){
                        if(color == c.roadcolor){
                            int currnum  = colorsum[c.curr][color].second-1;
                            int currsum = colorsum[c.curr][color].first - c.roadvalue;
                            
                            if(currnum == 1){
                                
                                pq.push(quadriple(c.value, pos, false, 0,0));
                            }else{
                                pq.push(quadriple(c.value+num, pos, true, color,num));
                                pq.push(quadriple(c.value+currsum, pos, false,0,0));
                            }
                        }else{
                            int currsum = colorsum[c.curr][color].first;
                            pq.push(quadriple(c.value+num, pos, true, color,num));
                            pq.push(quadriple(c.value+currsum, pos, false,0,0));
                        }
                    }else{
                        int currsum = colorsum[c.curr][color].first;
                        pq.push(quadriple(c.value+num, pos, true,color,num));
                        pq.push(quadriple(c.value+currsum,pos, false,0,0));
                    }
                }
            }

        }
    }
}

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].push_back(make_pair(b,make_pair(c,d)));
        neighbors[b].push_back(make_pair(a,make_pair(c,d)));
        colorsum[a][c].first +=d;
        colorsum[a][c].second+=1;
        colorsum[b][c].first+=d;
        colorsum[b][c].second+=1;
    }
    dijkstra(0);
    cout << dp[N-1] << endl;
}

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