我是将当前的010序列作为了一个值保存了，同时做标记。如果标记已经有了就不在从这个值继续扩展。具体的代码如下：

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int SIZE = 1 << 20 + 1;
class Operation
{
public:
	char opcode[21];
	int cost;
};

class Node
{
public:
	char str[21];
	int cost;
	Node() {}
	Node( char *s, int b ) { strcpy( str, s ), cost = b; }

public:
	bool operator < ( const Node &n ) const
	{
		return cost > n.cost;
	}
};

Operation ops[32];
char source[21], dest[21];
int l, op, w;
bool flag[SIZE];

int evaluate( char *p )
{
	int sum = 0;
	for( int i = 0; i < l; i++ )
		sum = ( sum << 1 ) + p[i] - '0';
	return sum;
}

void change( Node &node, Operation *o, Node tmp )
{
	char *code = o->opcode;

	node.cost = o->cost + tmp.cost;

	for( int i = 0; i < l; i++ )
	{
		switch( code[i] )
		{
		case 'N':
			node.str[i] = tmp.str[i];
			break;
		case 'F':
			if( tmp.str[i] == '1' )
				node.str[i] = '0';
			else
				node.str[i] = '1';
			break;
		case 'S':
			node.str[i] = '1';
			break;
		case 'C':
			node.str[i] = '0';
			break;
		}
	}

	node.str[l] = '\0';
}

void solve()
{
	int t, stop = evaluate( dest ), result = -1;
	memset( flag, false, sizeof( flag ) );
	priority_queue < Node > q;

	q.push( Node( source, 0 ) );

	while( !q.empty() )
	{
		Node tmp = q.top();
		q.pop();

		if( evaluate( tmp.str ) == stop )
		{
			result = tmp.cost;
			break;
		}

		for( int i = 0; i < op; i++ )
		{
			Node add;
			change( add, &ops[i], tmp );
			t = evaluate( add.str );

			if( !flag[t] )
			{
				flag[t] = true;
				q.push( add );
			}
		}
	}

	if( result != -1 )
		printf( "%d ", result );
	else
		printf( "%s ", "NP" );
}

int main()
{
	int t, i;
	freopen( "2908.txt", "r", stdin );

	for( scanf( "%d", &t ); t > 0; t-- )
	{
		scanf( "%d%d%d", &l, &op, &w );
		for( i = 0; i < op; i++ )
			scanf( "%s%d", ops[i].opcode, &ops[i].cost );

		for( i = 0; i < w; i++ )
		{
			scanf( "%s%s", source, dest );
			solve();
		}
		printf( "\n" );
	}
//	fclose( stdin );

	return 0;
}