oj.uz

Submission #637686

# Submission time Handle Problem Language Result Execution time Memory
637686 2022-09-02T17:36:48 Z chjiao Robot (JOI21_ho_t4) C++17
100 / 100
 685 ms 79032 KB 
#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<int, ll>> colorsum(MN);
//vector<vector<pair<int,pair<int,ll>>>> neighbors(MN);
vector<map<int,vector<pair<int,ll>>>> neighbors(MN);
vector<ll> dp(MN, LLONG_MAX);
map<int, ll> dp2[MN];
struct quadriple{
    ll value;      //当前的value （cost）
    int curr;      // node
    // bool changed;  //是否改变
    int roadcolor; //来的road的color
    // ll roadvalue;  //来的road的value  （cost）
	int preCurr;   //来的路径
};

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

void dijkstra(ll s) {
    priority_queue<quadriple, vector<quadriple>, cmp> pq;
    pq.push({0LL,1,0, 0});
    dp[1] =0;
    while (!pq.empty()) {
        quadriple c = pq.top(); 
        pq.pop();
        
        if(c.roadcolor !=0 ){ //来的时候改变了颜色
            if(dp2[c.curr][c.roadcolor] != c.value){
                continue;
            }
            for(auto& [nPos, nValue]: neighbors[c.curr][c.roadcolor]){ //first = pos, second.first = color, second.second = num|| (was 'a')
                int nColor = c.roadcolor;
                // tie(nColor, nValue) = x;

               // if (c.roadcolor != nColor) continue;
                ll currsum = c.value +colorsum[c.curr][nColor] - nValue;
                if( currsum <  dp[nPos] ) { //只考虑改变其他颜色
                    dp[nPos] = currsum;
                    pq.push({currsum, nPos, 0, c.curr}) ;
                }
            }

        }else{  //来的时候未改变了颜色
            if(dp[c.curr] != c.value){
                continue;
            }
            for(auto& [nColor, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
                for (auto & [nPos, nValue]: x) {
               // int nPos; ;ll nValue;
                

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

                    // //初始化DP2颜色
                    // if(dp2[nPos].count(nColor) == 0) dp2[nPos][nColor] = LLONG_MAX;

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

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

                    // case 3: 改变了目的路径颜色，下一步目的地颜色相同并同步改变
                    if( dp2[nPos].count(nColor)==0 ||c.value < dp2[nPos][nColor] ){
                        pq.push({c.value, nPos, nColor, 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); 
    int N,M,a,b,c; 
    ll d;
    cin >> N >> M;
    for(int i=0; i<M; i++){
        cin >> a >> b >> c >> d;
        neighbors[a][c].push_back(make_pair(b,d));
        neighbors[b][c].push_back(make_pair(a,d));
        colorsum[a][c] +=d;  //presum
        colorsum[b][c]+=d;
    }
    dijkstra(0);
	
    cout << ((dp[N] <= 1e18)?dp[N] :-1 )<< endl;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 8 ms 15188 KB Output is correct
4 Correct 7 ms 15188 KB Output is correct
5 Correct 8 ms 15228 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 9 ms 15316 KB Output is correct
8 Correct 8 ms 15188 KB Output is correct
9 Correct 11 ms 15700 KB Output is correct
10 Correct 10 ms 15700 KB Output is correct
11 Correct 9 ms 15660 KB Output is correct
12 Correct 11 ms 15444 KB Output is correct
13 Correct 10 ms 15572 KB Output is correct
14 Correct 9 ms 15572 KB Output is correct
15 Correct 8 ms 15444 KB Output is correct
16 Correct 9 ms 15444 KB Output is correct
17 Correct 12 ms 15496 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 8 ms 15444 KB Output is correct
20 Correct 8 ms 15444 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 33424 KB Output is correct
2 Correct 92 ms 24472 KB Output is correct
3 Correct 171 ms 30032 KB Output is correct
4 Correct 107 ms 27288 KB Output is correct
5 Correct 685 ms 76404 KB Output is correct
6 Correct 568 ms 66860 KB Output is correct
7 Correct 299 ms 56376 KB Output is correct
8 Correct 356 ms 46852 KB Output is correct
9 Correct 355 ms 46796 KB Output is correct
10 Correct 289 ms 45424 KB Output is correct
11 Correct 118 ms 30932 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 8 ms 15188 KB Output is correct
4 Correct 7 ms 15188 KB Output is correct
5 Correct 8 ms 15228 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 9 ms 15316 KB Output is correct
8 Correct 8 ms 15188 KB Output is correct
9 Correct 11 ms 15700 KB Output is correct
10 Correct 10 ms 15700 KB Output is correct
11 Correct 9 ms 15660 KB Output is correct
12 Correct 11 ms 15444 KB Output is correct
13 Correct 10 ms 15572 KB Output is correct
14 Correct 9 ms 15572 KB Output is correct
15 Correct 8 ms 15444 KB Output is correct
16 Correct 9 ms 15444 KB Output is correct
17 Correct 12 ms 15496 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 8 ms 15444 KB Output is correct
20 Correct 8 ms 15444 KB Output is correct
21 Correct 164 ms 33424 KB Output is correct
22 Correct 92 ms 24472 KB Output is correct
23 Correct 171 ms 30032 KB Output is correct
24 Correct 107 ms 27288 KB Output is correct
25 Correct 685 ms 76404 KB Output is correct
26 Correct 568 ms 66860 KB Output is correct
27 Correct 299 ms 56376 KB Output is correct
28 Correct 356 ms 46852 KB Output is correct
29 Correct 355 ms 46796 KB Output is correct
30 Correct 289 ms 45424 KB Output is correct
31 Correct 118 ms 30932 KB Output is correct
32 Correct 130 ms 29392 KB Output is correct
33 Correct 158 ms 30884 KB Output is correct
34 Correct 375 ms 50400 KB Output is correct
35 Correct 278 ms 42060 KB Output is correct
36 Correct 264 ms 47672 KB Output is correct
37 Correct 278 ms 50220 KB Output is correct
38 Correct 325 ms 59708 KB Output is correct
39 Correct 130 ms 32988 KB Output is correct
40 Correct 364 ms 52132 KB Output is correct
41 Correct 405 ms 52392 KB Output is correct
42 Correct 436 ms 60544 KB Output is correct
43 Correct 198 ms 37384 KB Output is correct
44 Correct 399 ms 43828 KB Output is correct
45 Correct 288 ms 47588 KB Output is correct
46 Correct 242 ms 47848 KB Output is correct
47 Correct 303 ms 50416 KB Output is correct
48 Correct 649 ms 79032 KB Output is correct