「TJOI2019」大中锋的游乐场

问题分析

比较明显的最短路模型。需要堆优化的dij。建图的时候注意细节就好。
参考程序

#include <bits/stdc++.h>

#define LL long long

//#define DEBUG

using namespace std;

const int Maxn = 10010;

const int Maxm = 100010;

const int Maxk = 12;

struct edge {

	int To, Next, Cost;

};

edge Edge[ Maxm << 1 ];

int Start[ Maxn ], Used;

int n, m, k, Tag[ Maxn ], Dis[ Maxn ][ Maxk << 1 ], s, t, Vis[ Maxn ][ Maxk << 1 ];

int DistK;

struct heap {

	int Used, Tree[ Maxn * ( Maxk << 1 ) ], Ref[ Maxn * ( Maxk << 1 ) ];

	void Clear() { Used = 0; return; }

	bool Cmp( int x, int y ) {

		return Dis[ x / DistK ][ x % DistK ] < Dis[ y / DistK ][ y % DistK ];

	}

	bool Empty() { return Used == 0; }

	inline void Swap( int x, int y ) {

		Ref[ Tree[ x ] ] = y;

		Ref[ Tree[ y ] ] = x;

		swap( Tree[ x ], Tree[ y ] );

		return;

	}

	void Insert( int x ) {

		++Used; Tree[ Used ] = x; Ref[ x ] = Used;

		int Temp = Used;

		for( ; Temp > 1; )

			if( Cmp( Tree[ Temp ], Tree[ Temp >> 1 ] ) )

				Swap( Temp, Temp >> 1 ), Temp >>= 1;

			else

				break;

		return;

	}

	void Fresh( int x ) {

		int Temp = Ref[ x ];

		for( ; Temp > 1; )

			if( Cmp( Tree[ Temp ], Tree[ Temp >> 1 ] ) )

				Swap( Temp, Temp >> 1 ), Temp >>= 1;

			else

				break;

		return;

	}

	int Top() { return Tree[ 1 ]; }

	void Pop() {

		Swap( 1, Used ); --Used;

		int Temp = 1;

		for( ; ( Temp << 1 ) <= Used; ) {

			if( ( Temp << 1 | 1 ) > Used ) {

				if( Cmp( Tree[ Temp << 1 ], Tree[ Temp ] ) )

					Swap( Temp, Temp << 1 );

				break;

			}

			if( Cmp( Tree[ Temp << 1 ], Tree[ Temp << 1 | 1 ] ) )

				if( Cmp( Tree[ Temp << 1 ], Tree[ Temp ] ) ) {

					Swap( Temp, Temp << 1 );

					Temp <<= 1;

				}

				else

					break;

			else

				if( Cmp( Tree[ Temp << 1 | 1 ], Tree[ Temp ] ) ) {

					Swap( Temp, Temp << 1 | 1 );

					Temp = Temp << 1 | 1;

				}

				else

					break;

		}

		return;

	}

};

heap Heap;

void Clear() {

	memset( Start, 0, sizeof( Start ) );

	Used = 0;

	memset( Dis, 255, sizeof( Dis ) );

	Heap.Clear();

	return;

}

inline void AddEdge( int x, int y, int z ) {

	Edge[ ++Used ] = ( edge ){ y, Start[ x ], z };

#ifdef DEBUG

	printf( "AddEdge %d -> %d : %d\n", x, y, z );

#endif

	Start[ x ] = Used;

	return;

}

void Init() {

	scanf( "%d%d%d", &n, &m, &k );

	++k;

	for( int i = 1; i <= n; ++i ) scanf( "%d", &Tag[ i ] );

	for( int i = 1; i <= n; ++i ) Tag[ i ] = ( Tag[ i ] == 1 ) ? -1 : 1;

	for( int i = 1; i <= m; ++i ) {

		int x, y, z; scanf( "%d%d%d", &x, &y, &z );

		AddEdge( x, y, z ); AddEdge( y, x, z );

	}

	scanf( "%d%d", &s, &t );

	DistK = k << 1;

	return;

}

void Work() {

	Clear();

	Init();

	Dis[ s ][ k + Tag[ s ] ] = 0;

	if( k + Tag[ s ] < 1 || k + Tag[ s ] >= DistK ) {

		printf( "-1\n" );

		return;

	}

	Heap.Insert( s * DistK + k + Tag[ s ] );

	Vis[ s ][ k ] = 2;

	for( ; !Heap.Empty(); ) {

		int T = Heap.Top();

		Heap.Pop();

		int u = T / DistK;

		Vis[ u ][ T % DistK ] = 1;

#ifdef DEBUG

		printf( "Sol %d %d %d\n", u, T % DistK, Dis[ u ][ T % DistK ] );

#endif

		for( int t = Start[ u ]; t; t = Edge[ t ].Next ) {

			int v = Edge[ t ].To; int p = T % DistK + Tag[ v ];

			if( p < 1 || p >= DistK ) continue;

			if( Vis[ v ][ p ] == 1 ) continue;

			if( Dis[ v ][ p ] == -1 ||

					Dis[ v ][ p ] > Dis[ u ][ T % DistK ] + Edge[ t ].Cost ) {

				Dis[ v ][ p ] = Dis[ u ][ T % DistK ] + Edge[ t ].Cost;

#ifdef DEBUG

				printf( "  Cha %d %d %d\n", v, p, Dis[ v ][ p ] );

#endif

				if( Vis[ v ][ p ] == 2 ) Heap.Fresh( v * DistK + p );

				else {

					Heap.Insert( v * DistK + p );

					Vis[ v ][ p ] = 2;

				}

			}

		}

	}

	int Ans = -1;

	for( int i = 1; i < DistK; ++i )

		if( Dis[ t ][ i ] != -1 && ( Ans == -1 || Ans > Dis[ t ][ i ] ) )

			Ans = Dis[ t ][ i ];

	printf( "%d\n", Ans );

	return;

}

int main() {

	int TestCases; scanf( "%d", &TestCases );

	for( ; TestCases--; ) Work();

	return 0;

}
巴特西

「TJOI2019」大中锋的游乐场

问题分析

参考程序

最新文章

热门文章
