제출 #637150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637150		chjiao	Robot (JOI21_ho_t4)	C++17	0 / 100	3103 ms	300016 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;
vector<map<int, pair<int,int>>> colorsum(MN);
vector<vector<pair<int,pair<int,int>>>> neighbors(MN);
vector<ll> dp(MN, LLONG_MAX);
map<int, bool> visited[MN];
struct quadriple{
    ll value;      //当前的value （cost）
    int curr;      // node
    bool changed;  //是否改变
    int roadcolor; //来的road的color
    ll roadvalue;  //来的road的value  （cost）
    quadriple(ll _value, int _curr, bool _changed, int _roadcolor, ll _roadvalue){
        value = _value;  
        curr = _curr;
        changed = _changed;
        roadcolor = _roadcolor;
        roadvalue = _roadvalue;
    }
};

struct cmp {
    bool operator ()(quadriple & a, quadriple& b){
		if(a.value == b.value) return a.curr > b.curr;
        return a.value > b.value;
    }
};

void dijkstra(int s) {
    priority_queue<quadriple, vector<quadriple>, cmp> pq;
    pq.push(quadriple(0,1,false,0,0));
    while (!pq.empty()) {
        quadriple c = pq.top(); 
        pq.pop();
        if(visited[c.curr][c.roadcolor] == false){
            visited[c.curr][c.roadcolor] = true;
            // dp[c.curr][c.changed] =c.value;
			dp[c.curr] = min(dp[c.curr], c.value);
            for(auto& [nPos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
                int nColor, nValue;
                tie(nColor, nValue) = x;
				// if(visited[nPos]) continue;
				int num  =   colorsum[c.curr][nColor].second; //colorsum[c.curr].find(nColor)->second.second;
				
                if(num ==1){ //相同颜色的路径数
                    pq.push(quadriple(c.value, nPos, false, nColor,0));
                }else{
                    if(c.changed == true){ //来的时候改变了颜色
                        if(nColor == c.roadcolor){ //来的颜色和去的颜色一样
                            
                            if(num == 2){
                                pq.push(quadriple(c.value, nPos, false, nColor,0));
                            }else{
                                pq.push(quadriple(c.value+ nValue, nPos, true, nColor, nValue));
								
								int currsum = colorsum[c.curr][nColor].first  - c.roadvalue - nValue;
                                pq.push(quadriple(c.value + currsum, nPos, false,nColor,0));
                            }
                        }else{  ////来的颜色和去的颜色不一样
                            pq.push(quadriple(c.value+ nValue, nPos, true, nColor,nValue));
					
							int currsum =  colorsum[c.curr][nColor].first  - nValue;
                            pq.push(quadriple(c.value+currsum, nPos, false,nColor,0));
                        }
                    }else{  //来的时候未改变了颜色
                        
                        pq.push(quadriple(c.value+nValue, nPos, true, nColor,nValue));
						int currsum = colorsum[c.curr][nColor].first - nValue;
                        pq.push(quadriple(c.value+currsum, nPos, false,nColor,0));
                    }
                }
            }

        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	// freopen("Robot.in", "r", stdin);
    // freopen("Robot.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;  //presum
        colorsum[a][c].second+=1;  // num of same color routes
        colorsum[b][c].first+=d;
        colorsum[b][c].second+=1;
    }
    dijkstra(0);
	
    cout << ((dp[N] != LLONG_MAX)?dp[N] :-1 )<< endl;
}

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