poj-1251

可憐啊,自己好不容易找了個prim的模板,然後花費不菲的時間使用printf(),scanf()來處理這麼復雜的數字,字母的問題居然調試通過了,雖然在最後提交時報告了超時,參考了一下網上的代碼,無非就是使用了很多的輸入輸出語句,這可能導致了大量的用時,算法代碼是一致的.先上正確的

#include
#include
#include
using namespace std;
#define INF 10000
#define MAX 50
#define MAXN 100
int n,m,v,sum;
int edge[MAX][MAX];
int lowcost[MAX];
int nextvex[MAX];
int prim(int u0,int n)
{
	int i,j;
	int sum=0;
	for(i=1;i<=n;i++)//初始化lowcost[i],nextvex[i]
	{
		lowcost[i]=edge[u0][i];
		nextvex[i]=u0;
	}
	nextvex[u0]=-1;
	for(i=1;i>n&&n){
	
	memset(edge,0,sizeof(edge));
	for(i=n;i>1;i--)
	{
		char a,e;
		int k;
		cin>>a>>k;
		for(j=1;j<=k;j++)

		{
			int cost;
			cin>>e>>cost;
			edge[a-64][e-64]=edge[e-64][a-64]=cost;

		}

	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)
				edge[i][j]=0;
			else if(edge[i][j]==0)
				edge[i][j]=INF;
		}
	}
	printf("%d\n",prim(1,n));

	}
	return 0;
}

#include
#include
#include
using namespace std;
#define INF 10000
#define MAX 50
#define MAXN 100
int n,m,v,sum;
int edge[MAX][MAX];
int lowcost[MAX];
int nextvex[MAX];
int prim(int u0,int n)
{
	int i,j;
	int sum=0;
	for(i=1;i<=n;i++)//初始化lowcost[i],nextvex[i]
	{
		lowcost[i]=edge[u0][i];
		nextvex[i]=u0;
	}
	nextvex[u0]=-1;
	for(i=1;i1;i--)
	{
		scanf("%c",&a);//城市A
		scanf("%c",&w);//消除換行符
		scanf("%d",&k);//與其他城市連接的道路數目
		for(j=1;j<=k;j++)

		{
			scanf("%c",&w);//消除影響
			scanf("%c",&e);//後一個城市
			scanf("%d",&cost);//權值
			edge[a-64][e-64]=edge[e-64][a-64]=cost;

		}
		scanf("%c",&w);//消除影響

	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)
				edge[i][j]=0;
			else if(edge[i][j]==0)
				edge[i][j]=INF;
		}
	}
	printf("%d\n",prim(1,n));

	}
	return 0;
}