제출 #634805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634805		mdn2002	Robot (JOI21_ho_t4)	C++14	34 / 100	3081 ms	71332 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n , m , dp [600005];
vector < int > gr [200005];
map < pair < int , int > , long long > col , pri , sumcol , redg;
vector < pair < int , int > > edg;
int main ()
{
    cin >> n >> m;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        edg . push_back ( { i , 0 } );
        redg [ { i , 0 } ] = i - 1;
    }
    for ( int i = 0 ; i < m ; i ++ )
    {
        int x , y;
        cin >> x >> y;
        redg [ { y , x } ] = edg . size ();
        edg . push_back ( { y , x } );
        redg [ { x , y } ] = edg . size ();
        edg . push_back ( { x , y } );
        gr [x] . push_back ( y );
        gr [y] . push_back ( x );
        cin >> col [ { x , y } ] >> pri [ { x , y } ];
        col [ { y , x } ] = col [ { x , y } ];
        pri [ { y , x } ] = pri [ { x , y } ];
        sumcol [ { x , col [ { x , y } ] } ] += pri [ { x , y } ];
        sumcol [ { y , col [ { x , y } ] } ] += pri [ { x , y } ];
    }
    for ( int i = 0 ; i <= n + m + m + 1 ; i ++ ) dp [i] = 1e16;
    dp [0] = 0;
    priority_queue < pair < long long , int > > q;
    q . push ( { 0 , 0 } );
    long long ans = 1e16;
    while ( q . size () )
    {
        pair < long long , int > p = q . top ();
        q . pop ();
        int ind = p . second;
        int x = edg [ind] . first , last = edg [ind] . second;
        if ( x == n ) ans = min ( ans , dp [ind] );
        for ( auto u : gr [x] )
        {
            long long sum = sumcol [ { x , col [ { x , u } ] } ];
            sum -= pri [ { x , u } ];
            if ( last && col [ { x , last } ] == col [ { x , u } ] ) sum -= pri [ { x , last } ];
            int indd = redg [ { u , 0 } ];
            if ( dp [ind] + sum < dp [indd] )
            {
                dp [indd] = dp [ind] + sum;
                q . push ( { - dp [indd] , indd } );
            }
            indd = redg [ { u , x } ];
            if ( dp [ind] + pri [ { x , u } ] < dp [indd] )
            {
                dp [indd] = dp [ind] + pri [ { x , u } ];
                q . push ( { - dp [indd] , indd } );
            }
        }
    }
    if ( ans == 1e16 ) cout << -1;
    else cout << ans;
}

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