Submission #634865

#	Time	Username	Problem	Language	Result	Execution time	Memory
634865		mdn2002	Robot (JOI21_ho_t4)	C++14	100 / 100	1121 ms	92296 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

struct edgg {
    long long b , c , p;
};
long long n , m;
map < int , vector < edgg > > gr [100005];
map < int , long long > sum [100005] , dp [100005];
priority_queue < pair < long long , pair < int , int > > > q;
void add ( int x , int y , long long ad )
{
    if ( dp [x] . count ( y ) == 0 || dp [x][y] > ad )
    {
        dp [x][y] = ad;
        q . push ( { - ad , { x , y } } );
    }
}
int main ()
{
    scanf ( "%lld%lld" , &n , &m );

    for ( int i = 0 ; i < m ; i ++ )
    {
        long long x , y , c , p;
        scanf ( "%lld%lld%lld%lld" , &x , &y , &c , &p );

        gr [y][c] . push_back ( { x , c , p } );

        gr [x][c] . push_back ( { y , c , p } );

        sum [x][c] += p;
        sum [y][c] += p;
    }

    dp [1][0] = 0;
    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 ( - p . first != dp [x][last] ) continue;
        if ( x == n && last == 0 ) ans = min ( ans , dp [x][last] );
        if ( last == 0 )
        {
            for ( auto xx : gr [x] )
            {
                for ( auto uu : xx . second )
                {
                    long long u = uu . b , c = uu . c , p = uu . p , summ = sum [x][c] - p;

                    add ( u , 0 , dp [x][last] + summ );
                    add ( u , 0 , dp [x][last] + p );
                    add ( u , c , dp [x][last] );

                }
            }
        }
        else
        {
            for ( auto uu : gr [x][last] )
            {
                long long u = uu . b , c = uu . c , p = uu . p , summ = sum [x][c] - p;
                int indd = u - 1;
                add ( u , 0 , dp [x][last] + summ );
            }
        }
    }
    if ( ans == 1e16 ) printf ( "-1" );
    else printf ( "%lld" , ans );
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:75:21: warning: unused variable 'indd' [-Wunused-variable]
   75 |                 int indd = u - 1;
      |                     ^~~~
Main.cpp:28:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf ( "%lld%lld" , &n , &m );
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf ( "%lld%lld%lld%lld" , &x , &y , &c , &p );
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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