Submission #1139423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139423		kitkat12	Robot (JOI21_ho_t4)	C++20	0 / 100	244 ms	38252 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

const int nmax = 1e5+3;
const ll inf = 1e18;
vector<array<ll,3>> adj[nmax];

map<int,pii> cf[nmax]; // color freq for each city

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,a,b,c;
    ll p ;
    cin>>n>>m;
    li(i,0,m){
        cin>>a>>b>>c>>p;
        adj[a].pb({b,c,p});
        adj[b].pb({a,c,p});
        cf[a][c].F++; cf[a][c].S+=p;

        cf[b][c].F++; cf[b][c].S+=p;
    }

    // dijk
    vector<ll> d(nmax,inf);
    d[1]=0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0,1});
    while(!pq.empty()){
        const auto [d_v, v] = pq.top();
        pq.pop();
        if(d_v!=d[v])continue;
        for(const auto [to, col, cost] : adj[v]){
            if(cf[v][col].F==1 && d_v < d[to]){
                d[to]=d_v;
                pq.push({d[to],to});
            }
            else if(cf[v][col].F!=1 && d_v + min(cost, cf[v][col].S-cost) < d[to]){
                d[to]=d_v+min(cost, cf[v][col].S-cost);
                pq.push({d[to],to});
            }
        }
    }
    if(d[n]==inf){
        cout<<-1<<endl;
    }
    else{
        cout<<d[n]<<endl;
    }

    return 0;
}
 

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