UVa 1235 – Anti Brute Force Lock

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3676

每次都取距離目前生成樹最小且尚未加入的點，加到生成樹的集合，最後即會得到最小生成樹(Minimum Spanning Tree)。這是Prim演算法的中心思想，和Dijkstra都採取相近的Greedy策略。

一棵最小生成樹

同樣的，這題可以將一組密碼當成一點，任意兩點之間都有邊，意思是每一組密碼都有可能由其他任一組轉過來，然後各條邊的權重就是從一組密碼轉成另外一組所轉動的次數，而因為最後所有點都包含在最小生成樹裡，所以起點設誰都沒關係。

最後所有的轉動次數就等同於MST的權重和 + 由0000轉到任一組密碼的最少轉動次數。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 501;
const int INF = 10000;

int key[MAXN];
int cost[MAXN][MAXN];
int dist[MAXN];
bool vst[MAXN];

int abs(int x)
{
	if(x < 0) return -x;
	else return x;
}

int compute(int Key1, int Key2)
{
	int d1, d2;
	int roll = 0;
	int dif;
	
	for(int k = 1; k <= 4; k++)
	{
		d1 = Key1 % 10, d2 = Key2 % 10;
		dif = abs(d1 - d2);
		roll += min(dif, 10 - dif);
		Key1 /= 10, Key2 /= 10;
	}
	
	return roll;
}

int main()
{
	int test;
	int n;
	int total;
	
	cin >> test;
	while(test--)
	{
		cin >> n;
		for(int i = 1; i <= n; i++)
			cin >> key[i];
		
		for(int i = 1; i <= n; i++)
			for(int j = i + 1; j <= n; j++)
				cost[i][j] = cost[j][i] = compute(key[i], key[j]);
			
		
		for(int i = 1; i <= n; i++)
		{
			dist[i] = INF;
			vst[i] = false;
		}
		
		total = INF;
		for(int i = 1; i <= n; i++)
			total = min(total, compute(0000, key[i]));
		
		
		dist[1] = 0;
		
		int min, now;
		for(int k = 1; k <= n; k++)
		{
			min = INF;
			for(int i = 1; i <= n; i++)
			{
				if(!vst[i] && dist[i] < min)
				{
					min = dist[i];
					now = i;
				}
			}
			
			dist[now] = 0;
			vst[now] = true;
	
			for(int i = 1; i <= n; i++)
			{
				if(!vst[i] && cost[now][i] < dist[i])
				{
					dist[i] = cost[now][i];
				}
			}
			
			total += min;
		}
		
		cout << total << endl;
	}


	return 0;
}