Submission #634810

#	Time	Username	Problem	Language	Result	Execution time	Memory
634810		mdn2002	Robot (JOI21_ho_t4)	C++14	0 / 100	3083 ms	150388 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n , m , dp [600005];
vector < int > gr [100005];
unordered_map < int , long long > col [100005] , pri [100005] , sumcol [200005] , redg [100005];
vector < pair < int , int > > edg;
int main ()
{
    scanf ( "%lld%lld" , &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;
        scanf ( "%d%d" , &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 ( sum == 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 ) printf ( "-1" );
    else printf ( "%lld" , ans );
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:9:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf ( "%lld%lld" , &n , &m );
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:18:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf ( "%d%d" , &x , &y );
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~

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