제출 #718439

#제출 시각아이디문제언어결과실행 시간메모리
718439vinnipuh01Robot (JOI21_ho_t4)C++17
34 / 100
45 ms24532 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> #define int long long #define sqrt sqrtl using namespace std; const long long oo = 1000000000000000000; long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen ( "sum.in", "r", stdin ) */ struct Node { int dp, u, pr, col; }; struct cmp { bool operator () ( const Node& a, const Node& b ) const { if ( a.dp == b.dp ) { if ( a.u == b.u ) { if ( a.pr == b.pr ) { return a.col < b.col; } return a.pr < b.pr; } return a.u < b.u; } return a.dp < b.dp; } }; int n, m, x, y, z[ 2001 ], t[ 2001 ]; int mp[ 2001 ][ 2001 ]; vector <pair<int, int> > v[ 2001 ]; int dp[ 2001 ][ 2001 ][ 2 ]; set <Node, cmp > st; void dfs( int u, int pr, int col ) { int num = 0; int pos = 0; if ( col == 1 ) { for ( auto to : v[ u ] ) { if ( to.first == pr ) num = t[ to.second ], pos = z[ to.second ]; } } int sum; for ( auto to : v[ u ] ) { if ( to.first == pr ) continue; if ( z[ to.second ] == pos ) sum = num; else sum = 0; if ( dp[ to.first ][ u ][ 1 ] > dp[ u ][ pr ][ col ] + t[ to.second ] ) { dp[ to.first ][ u ][ 1 ] = dp[ u ][ pr ][ col ] + t[ to.second ]; dfs( to.first, u, 1 ); } if ( dp[ to.first ][ u ][ 0 ] > dp[ u ][ pr ][ col ] + mp[ u ][ z[ to.second ] ] - t[ to.second ] - sum ) { dp[ to.first ][ u ][ 0 ] = dp[ u ][ pr ][ col ] + mp[ u ][ z[ to.second ] ] - t[ to.second ] - sum; dfs( to.first, u, 0 ); } } } main () { cin >> n >> m; for ( int i = 1; i <= m; i ++ ) { cin >> x >> y >> z[ i ] >> t[ i ]; mp[ x ][ z[ i ] ] += t[ i ]; mp[ y ][ z[ i ] ] += t[ i ]; v[ x ].push_back( { y, i } ); v[ y].push_back( { x, i } ); } for ( int i = 2; i <= n; i ++ ) { for ( int j = 1; j <= n; j ++ ) dp[ i ][ j ][ 1 ] = dp[ i ][ j ][ 0 ] = oo; } st.insert( { 0, 1, 0, 0 } ); while ( st.size() ) { Node u = *st.begin(); st.erase( st.begin() ); num = pos = 0; if ( u.col == 1 ) { for ( auto to : v[ u.u ] ) { if ( to.first == u.pr ) { num = t[ to.second ], pos = z[ to.second ]; } } } for ( auto to : v[ u.u ] ) { if ( to.first == u.pr ) continue; sum = 0; if ( z[ to.second ] == pos ) sum = num; if ( dp[ to.first ][ u.u ][ 1 ] > u.dp + t[ to.second ] ) { st.erase( { dp[ to.first ][ u.u ][ 1 ], to.first, u.u, 1 } ); dp[ to.first ][ u.u ][ 1 ] = u.dp + t[ to.second ]; st.insert( { dp[ to.first ][ u.u ][ 1 ], to.first, u.u, 1 } ); } if ( dp[ to.first ][ u.u ][ 0 ] > u.dp + mp[ u.u ][ z[ to.second ] ] - t[ to.second ] - sum ) { st.erase( { dp[ to.first ][ u.u ][ 0 ], to.first, u.u, 0 } ); dp[ to.first ][ u.u ][ 0 ] = u.dp + mp[ u.u ][ z[ to.second ] ] - t[ to.second ] - sum; st.insert( { dp[ to.first ][u.u ][ 0 ], to.first, u.u, 0 } ); } } } mn = oo; for ( int i = 1; i <= n; i ++ ) mn = min( mn, min( dp[ n ][ i ][ 1 ], dp[ n ][ i ][ 0 ] ) ); if ( mn == oo ) cout << "-1\n"; else cout << mn << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...