Submission #637269

#	Time	Username	Problem	Language	Result	Execution time	Memory
637269		chjiao	Robot (JOI21_ho_t4)	C++14	34 / 100	3059 ms	52156 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define newl '\n'
const ll mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const ll MN = 1e5+1;
vector<map<ll, pair<ll,ll>>> colorsum(MN);
vector<vector<pair<ll,pair<ll,ll>>>> neighbors(MN);
vector<ll> dp(MN, LLONG_MAX);
map<int, ll> dp2[MN];
// map<ll, bool> visited[MN];
struct quadriple{
    ll value;      //当前的value （cost）
    ll curr;      // node
    bool changed;  //是否改变
    ll roadcolor; //来的road的color
    ll roadvalue;  //来的road的value  （cost）
	ll preCurr;   //来的路径
    quadriple(ll _value, ll _curr, bool _changed, ll _roadcolor, ll _roadvalue, ll _preCurr){
        value = _value;  
        curr = _curr;
        changed = _changed;
        roadcolor = _roadcolor;
        roadvalue = _roadvalue;
		preCurr = _preCurr;
    }
};

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(ll s) {
    priority_queue<quadriple, vector<quadriple>, cmp> pq;
    pq.push(quadriple(0LL,1,false,0,0LL, 0));
    while (!pq.empty()) {
        quadriple c = pq.top(); 
        pq.pop();
        
        for(auto& [nPos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')

            ll nColor; ;ll nValue;
            tie(nColor, nValue) = x;

            //禁止原路返回
            if(nPos == c.preCurr) continue;

            //初始化DP2颜色
            if(dp2[nPos].count(nColor) == 0) dp2[nPos][nColor] = LLONG_MAX;
        
            if(c.changed == true ){ //来的时候改变了颜色
                if (c.roadcolor != nColor) continue;
                ll currsum = c.value +colorsum[c.curr][nColor].first  - nValue;
                if( currsum <  dp[nPos] ) { //只考虑改变其他颜色
                    dp[nPos] = currsum;
                    pq.push(quadriple(currsum, nPos, false,nColor,nValue, c.curr)) ;
                }
    
            }else{  //来的时候未改变了颜色

                // case 1: 不改变nColor的颜色，但是改变其他所有相同颜色路径的颜色（含不改变任何颜色，但没有其他相同颜色路径时）
                 ll currsum = c.value + colorsum[c.curr][nColor].first  - nValue;
                 if(currsum < dp[nPos]){
                    dp[nPos] = currsum;
                    pq.push(quadriple(currsum, nPos, false, nColor,nValue, c.curr));
                 }

                // case 2:  改变nColor的颜色，但是nColor的颜色和下一步的目的地颜色不同；
                currsum = c.value + nValue;
                if(currsum < dp[nPos]){
                    dp[nPos] = currsum;
                    pq.push(quadriple(currsum, nPos, false, nColor,nValue, c.curr));
                 }

                // case 3: 改变了目的路径颜色，下一步目的地颜色相同并同步改变
                if(c.value < dp2[nPos][nColor] ){
                    pq.push(quadriple(c.value, nPos, true, nColor,nValue, c.curr));
                    dp2[nPos][nColor] = c.value ;
                }
            }
        
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	//freopen("Robot.in", "r", stdin);
    // freopen("Robot.out", "w", stdout); 
    ll N,M,a,b,c,d;
    cin >> N >> M;
    for(ll 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] <= 1e18)?dp[N] :-1 )<< endl;
}

Compilation message (stderr)

Main.cpp: In function 'void dijkstra(long long int)':
Main.cpp:44:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for(auto& [nPos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
      |                   ^

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