Submission #634820

#	Time	Username	Problem	Language	Result	Execution time	Memory
634820		mdn2002	Robot (JOI21_ho_t4)	C++14	0 / 100	3119 ms	1053400 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct edg {
    int a , b , c , p , ind;
};

struct edgg {
    int b , c , p , ind , sum;
};
long long n , m , dp [600005] , summ [200005];
vector < edgg > gr [100005];
vector < edg > edgs;
int main ()
{
    scanf ( "%lld%lld" , &n , &m );
    for ( int i = 1 ; i <= n ; i ++ )
    {
        edgs . push_back ( { i , 0 , 0 , 0 , i - 1 } );
    }

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

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

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

    }
    for ( int i = 1 ; i <= n ; i ++ )
    {
        for ( auto x : gr [i] ) summ [ x . c ] += x . p;
        for ( int j = 0 ; j < gr [i] . size () ; j ++ ) gr [i][j] . sum = summ [ gr [i][j] . c ];
        for ( auto x : gr [i] ) summ [ x . c ] = 0;
    }

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

            int indd = u - 1;

            if ( dp [ind] + sum < dp [indd] )
            {
                dp [indd] = dp [ind] + sum;
                q . push ( { - dp [indd] , indd } );
            }

            indd = uu . ind;
            if ( dp [ind] + p < dp [indd] )
            {
                dp [indd] = dp [ind] + p;
                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:26:32: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   26 |         gr [y] . push_back ( { x , c , p , edgs . size () , 0 } );
      |                                ^
Main.cpp:26:36: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   26 |         gr [y] . push_back ( { x , c , p , edgs . size () , 0 } );
      |                                    ^
Main.cpp:26:40: warning: narrowing conversion of 'p' from 'long long int' to 'int' [-Wnarrowing]
   26 |         gr [y] . push_back ( { x , c , p , edgs . size () , 0 } );
      |                                        ^
Main.cpp:26:56: warning: narrowing conversion of 'edgs.std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   26 |         gr [y] . push_back ( { x , c , p , edgs . size () , 0 } );
      |                                            ~~~~~~~~~~~~^~
Main.cpp:27:30: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   27 |         edgs . push_back ( { x , y , c , p , edgs . size () } );
      |                              ^
Main.cpp:27:34: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   27 |         edgs . push_back ( { x , y , c , p , edgs . size () } );
      |                                  ^
Main.cpp:27:38: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   27 |         edgs . push_back ( { x , y , c , p , edgs . size () } );
      |                                      ^
Main.cpp:27:42: warning: narrowing conversion of 'p' from 'long long int' to 'int' [-Wnarrowing]
   27 |         edgs . push_back ( { x , y , c , p , edgs . size () } );
      |                                          ^
Main.cpp:27:58: warning: narrowing conversion of 'edgs.std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   27 |         edgs . push_back ( { x , y , c , p , edgs . size () } );
      |                                              ~~~~~~~~~~~~^~
Main.cpp:29:32: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   29 |         gr [x] . push_back ( { y , c , p , edgs . size () , 0 } );
      |                                ^
Main.cpp:29:36: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   29 |         gr [x] . push_back ( { y , c , p , edgs . size () , 0 } );
      |                                    ^
Main.cpp:29:40: warning: narrowing conversion of 'p' from 'long long int' to 'int' [-Wnarrowing]
   29 |         gr [x] . push_back ( { y , c , p , edgs . size () , 0 } );
      |                                        ^
Main.cpp:29:56: warning: narrowing conversion of 'edgs.std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   29 |         gr [x] . push_back ( { y , c , p , edgs . size () , 0 } );
      |                                            ~~~~~~~~~~~~^~
Main.cpp:30:30: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   30 |         edgs . push_back ( { y , x , c , p , edgs . size () } );
      |                              ^
Main.cpp:30:34: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   30 |         edgs . push_back ( { y , x , c , p , edgs . size () } );
      |                                  ^
Main.cpp:30:38: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   30 |         edgs . push_back ( { y , x , c , p , edgs . size () } );
      |                                      ^
Main.cpp:30:42: warning: narrowing conversion of 'p' from 'long long int' to 'int' [-Wnarrowing]
   30 |         edgs . push_back ( { y , x , c , p , edgs . size () } );
      |                                          ^
Main.cpp:30:58: warning: narrowing conversion of 'edgs.std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   30 |         edgs . push_back ( { y , x , c , p , edgs . size () } );
      |                                              ~~~~~~~~~~~~^~
Main.cpp:36:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edgg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for ( int j = 0 ; j < gr [i] . size () ; j ++ ) gr [i][j] . sum = summ [ gr [i][j] . c ];
      |                           ~~^~~~~~~~~~~~~~~~~~
Main.cpp:15:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf ( "%lld%lld" , &n , &m );
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:24:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf ( "%lld%lld%lld%lld" , &x , &y , &c , &p );
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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