Submission #634801

#	Time	Username	Problem	Language	Result	Execution time	Memory
634801		mdn2002	Robot (JOI21_ho_t4)	C++14	0 / 100	3077 ms	10004 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n , m , dp [1003][1003];
vector < int > gr [200005];
long long col [1003][1003] , pri [1003][1003] , sumcol [1003][2003];
int main ()
{
    cin >> n >> m;
    for ( int i = 0 ; i < m ; i ++ )
    {
        int x , y;
        cin >> 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 [x][ col [x][y] ] += pri [x][y];
    }
    for ( int i = 1 ; i <= n ; i ++ )
    {
        for ( int j = 0 ; j <= n ; j ++ ) dp [i][j] = 1e16;
    }
    dp [1][0] = 0;
    priority_queue < pair < long long , pair < int , int > > > q;
    q . push ( { 0 , { 1 , 0 } } );
    long long ans = 1e16;
    while ( q . size () )
    {
        pair < long long , pair < int , int > > p = q . top ();
        q . pop ();
        int x = p . second . first , last = p . second . second;
        if ( x == n ) ans = min ( ans , dp [x][last] );
        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];
            if ( dp [x][last] + sum < dp [u][0] )
            {
                dp [u][0] = dp [x][last] + sum;
                q . push ( { dp [u][0] , { u , 0 } } );
            }
            if ( dp [x][last] + pri [x][u] < dp [u][x] )
            {
                dp [u][x] = dp [x][last] + pri [x][u];
                q . push ( { dp [u][x] , { u , x } } );
            }
        }
    }
    if ( ans == 1e16 ) cout << -1;
    else cout << ans;
}

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