Submission #680701

#	Time	Username	Problem	Language	Result	Execution time	Memory
680701		vinnipuh01	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	167 ms	4052 KiB

ho_t4

#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 sqrt sqrtl

using namespace std;

const long long oo = 1e18;

long long sum, ans = 0, mx = 0, mn = oo, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;


    freopen ( "sum.in", "r", stdin )
*/


int n, m, x[ 50001 ], y[ 50001 ], a[ 50001 ], b[ 50001 ];
long long dp[ 201 ][ 201 ], d[ 201 ];
int p[ 201 ], pp[ 201 ], used[ 201 ];
long long dpp[ 201 ][ 201 ];
vector <pair<int, int> > v[ 222 ], vv[ 222 ];
set <pair<int, int> > st;
int mp[ 50001 ];

void dfs( int u ) {
	for ( int i = 1; i <= n; i ++ ) {
		d[ i ] = oo;
		p[ i ] = -1;
		used[ i ] = pp[ i ] = 0;
	}
	d[ u ] = 0;
	while ( true ) {
		num = -1;
		for ( int i = 1; i <= n; i ++ ) {
			if ( used[ i ] )
				continue;
			if ( num == -1 || d[ i ] < d[ num ] )
				num = i;
		}
		if ( num == -1 || d[ num ] == oo )
			break;
		used[ num ] = 1;
		for ( auto to : v[ num ] ) {
			if ( d[ to.first ] > d[ num ] + a[ to.second ] ) {
				d[ to.first ] = d[ num ] + a[ to.second ];
				p[ to.first ] = num;
				pp[ to.first ] = to.second;
			}
		}
	} 
}

void dfss( int u ) {
	for ( int i = 1; i <= n; i ++ ) {
		d[ i ] = oo;
		p[ i ] = -1;
		used[ i ] = pp[ i ] = 0;
	}
	d[ u ] = 0;
	while ( true ) {
		num = -1;
		for ( int i = 1; i <= n; i ++ ) {
			if ( used[ i ] )
				continue;
			if ( num == -1 || d[ i ] < d[ num ] )
				num = i;
		}
		if ( num == -1 || d[ num ] == oo )
			break;
		used[ num ] = 1;
		for ( auto to : vv[ num ] ) {
			if ( d[ to.first ] > d[ num ] + a[ to.second ] ) {
				d[ to.first ] = d[ num ] + a[ to.second ];
				p[ to.first ] = num;
				pp[ to.first ] = to.second;
			}
		}
	}
}

main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x[ i ] >> y[ i ] >> a[ i ] >> b[ i ];
		v[ x[ i ] ].push_back( { y[ i ], i } );	
		vv[ y[ i ] ].push_back( { x[ i ], i } );
	}
	dfss( 1 );
	for ( int i = 1; i <= n; i ++ )
		dpp[ i ][ 1 ] = d[ i ];
	dfss( n );
	for ( int i = 1; i <= n; i ++ )
		dpp[ i ][ n ] = d[ i ];
	dfs( 1 );
	for ( int i = 1; i <= n; i ++ )
		dp[ 1 ][ i ] = d[ i ];
	for ( int i = n; i != -1; i = p[ i ] )
		mp[ pp[ i ] ] = 1;
	dfs( n );
	for ( int i = 1; i <= n; i ++ )
		dp[ n ][ i ] = d[ i ];
	for ( int i = 1; i != -1; i = p[ i ] )
		mp[ pp[ i ] ] = 1;
	ans = oo;
	if ( dp[ 1 ][ n ] != oo && dp[ n ][ 1 ] != oo )
		ans = dp[ 1 ][ n ] + dp[ n ][ 1 ];
	for ( int i = 1; i <= m; i ++ ) {
		if ( mp[ i ] ) {
			for ( int j = 0; j < v[ x[ i ] ].size(); j ++ ) {
				if ( v[ x[ i ] ][ j ].second == i ) {
					v[ x[ i ] ].erase( v[ x[ i ] ].begin() + j );
					break;
				}
			}
			v[ y[ i ] ].push_back( { x[ i ], i } );
			dfs( 1 );
			sum = d[ n ];
			dfs( n );
			if ( sum != oo && d[ 1 ] != oo )
				ans = min( ans, d[ 1 ] + sum + b[ i ] );
			v[ y[ i ] ].pop_back();
			v[ x[ i ] ].push_back( { y[ i ], i } );
		}
		else {
			num = dp[ 1 ][ n ];
			sum = dp[ n ][ 1 ];
			num = min( num, dp[ 1 ][ y[ i ] ] + a[ i ] + dpp[ x[ i ] ][ n ] + 0ll );
			sum = min( sum, dp[ n ][ y[ i ] ] + a[ i ] + dpp[ x[ i ] ][ 1 ] + 0ll );
//			cout << num << " " << sum << " " << b[ i ] << "\n";
			if ( num != oo && sum != oo )
				ans = min( sum + num + b[ i ], ans );
		}
//		cout << i << " - " << ans << "\n";
	}
	if ( ans == oo )
		cout << "-1";
	else
		cout << ans;
}

/*

dp[ 1 ][ y ] + a[ i ] + b[ i ] + dp[ x ][ n ]
dp[ n ][ x ] + a[ i ] + b[ i ] + dp[ x ][ 1 ]


*/

Compilation message (stderr)

ho_t4.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main () {
      | ^~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |    for ( int j = 0; j < v[ x[ i ] ].size(); j ++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63