Submission #523076

#	Time	Username	Problem	Language	Result	Execution time	Memory
523076		CaroLinda	Robot (JOI21_ho_t4)	C++14	100 / 100	1616 ms	113108 KiB

Main

#include <bits/stdc++.h>

#define pii pair<int,int>
#define ll long long
#define mk make_pair

const int MAXN = 1e5+10 ;
const int MAXM = 2e5+10 ;
const ll inf = 1e18+10LL ;

using namespace std ;

int N , M ;
int cor[MAXM*2] ;
int j[MAXM*2] ;
ll p[MAXM*2] ;
map< pair<int, int> , ll > custo ;
map< pair<int,int> , int > chave ;
vector<int> adj[MAXN] ;
vector<pair<int,ll> > graph[MAXM*3] ;

void add(pair<int,int> par , ll val ){
    if(custo.find(par) == custo.end()) custo[par] = 0 ;
    custo[par] += val ;
}

int main()
{
    ios_base::sync_with_stdio(false) ;
    cin.tie(0) ;

    cin >> N >> M ;

    for(int i = 0 , a , b ; i < 2*M ; i += 2 ){
        
        cin >> a >> b >> cor[i] >> p[i] ;
        
        j[i] = b ;
        j[i+1] = a ;
        cor[i+1] = cor[i] ;
        p[i+1] = p[i] ;

        add( mk(a,cor[i]) , p[i] ) ;
        add( mk(b,cor[i]) , p[i] ) ;

        chave[mk(a,cor[i])] = chave[mk(b,cor[i])] = 0 ;

        adj[a].push_back(i) ;
        adj[b].push_back(i+1) ;
    }

    for(int i = 1 ; i <= N ; i++ ) chave[mk(i,0)] = 0 ;

    int Key = 0 ;
    for(auto &e : chave ) e.second = ++Key ;

    for(int i = 1 ; i <= N ; i++ ){

        int x = chave[mk(i,0)] ;

        for(auto e : adj[i] ){

            int y = chave[mk(i,cor[e])] ;
            int a = chave[mk(j[e],0)] ;
            int b = chave[mk(j[e],cor[e])] ;

            graph[a].push_back( make_pair( y , custo[mk(i,cor[e])] - p[e] ) ) ;
            graph[b].push_back( make_pair( x, 0 ) ) ;
            graph[a].push_back( make_pair( x, p[e] ) ) ;
        }
    }

    for(auto e : chave )
        if(e.first.second) graph[ e.second ].push_back( mk( chave[mk(e.first.first,0)], 0 ) ) ;

    vector<ll> dist(Key+1, inf ) ;

    int T = chave[ mk(N,0) ] ;

    priority_queue<pair<ll,int> , vector<pair<ll,int> > , greater<pair<ll,int> > > fila ;

    fila.push( mk( dist[T] = 0 , T ) ) ;

    while(!fila.empty()){

        int x = fila.top().second ;
        ll d = fila.top().first ;

        fila.pop() ;

        if(d != dist[x]) continue ;

        for(auto e : graph[x]){

            ll newD = d + e.second ;
            int viz = e.first ;

            if(newD >= dist[viz]) continue ;

            fila.push( make_pair(dist[viz] = newD , viz) ) ;

        }

    }

    int S = chave[ mk(1,0) ] ;

    if(dist[S] == inf ) dist[S] = -1 ;

    cout << dist[S] << "\n" ;

}

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