제출 #1002568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002568		walizamanee	Robot (JOI21_ho_t4)	C++17	100 / 100	206 ms	33272 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int aa , m , one , two , col;
long long p , ans[200001] , an[200001] , choto[200001] , chek[200001] , uttor;
vector<pair<pair<int , long long> , int>> arr[200001]; //first e col , then price , then node
priority_queue<pair<long long , int> , vector<pair<long long , int>> , greater<pair<long long , int>>> pq;

int main() {
   
   cin >> aa >> m;
   for( int z = 0; z < m; z++ ) {
      cin >> one >> two >> col >> p;
      arr[one].push_back({{col , p} , two});
      arr[two].push_back({{col , p} , one});
   }
   for( int z = 1; z <= aa; z++ ) {
      sort( arr[z].begin() , arr[z].end() );
   }
   ans[1] = 1;
   pq.push({1 , 1});
   while( !pq.empty() ) {
       if( chek[pq.top().second] == 0 ) {
         chek[pq.top().second] = 1;
         one = pq.top().second;
         ans[one] = pq.top().first;
         two = arr[one].size();
         for( int z = 0; z < two; z++ ) {
            an[arr[one][z].first.first] += arr[one][z].first.second;
            if(choto[arr[one][z].first.first] == 0 ) choto[arr[one][z].first.first] = ans[one];
            if( ans[arr[one][z].second] != 0 ) {
               choto[arr[one][z].first.first] = min( ans[arr[one][z].second] , choto[arr[one][z].first.first] );
            }
         }
         for( int z = 0; z < two; z++ ) {
            if( chek[arr[one][z].second] == 0 ) {
               uttor = min( (min(arr[one][z].first.second , an[arr[one][z].first.first] - arr[one][z].first.second) + ans[one] ) ,  (an[arr[one][z].first.first] - arr[one][z].first.second) + choto[arr[one][z].first.first] );
               pq.push({uttor , arr[one][z].second});
            }
         }
         for( int z = 0; z < two; z++ ) {
            an[arr[one][z].first.first] = 0;
            choto[arr[one][z].first.first] = 0;
         }
       }
       else pq.pop();
   }
   cout << ans[aa] - 1;
   return 0;
}

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