POJ 2421 Constructing Roads

題目

輸入鄰接矩陣

再 輸入 已連接的兩個點

輸出 最短路徑

解析

可以將已連接的兩個點的原路徑長度 置為 0

再用prim算法求解 

 #include<iostream>   
using namespace std;  
#define N 105   
#define Max 0x7ffff   
int s[N][N],dist[N],flag[N];  
int minn(int a,int b)  
{  
    return a<b?a:b;  
}  
void print(int n)  
{  
    int i;  
    for(i=1;i<=n;i++)cout<<dist[i]<<" ";  
    cout<<endl;  
    for(i=1;i<=n;i++)cout<<flag[i]<<" ";  
    cout<<endl;  
}  
int prim(int n)  
{  
    int now,t,i,min,sum=0,minx;  
    for(i=1;i<=n;i++)dist[i]=s[1][i];  
    flag[1]=1;  
    for(t=1;t<n;t++)  
    {  
        minx=Max;  
        for(i=1;i<=n;i++)if(!flag[i]&&minx>dist[i])  
        {  
            min=i;  
            minx=dist[i];  
        }  
        sum+=dist[min];  
        flag[min]=1;  
        now=min;  
        for(i=1;i<=n;i++)  
            if(!flag[i]&&dist[i]>s[now][i])dist[i]=s[now][i];  
    }  
    return sum;  
      
  
}  
int main()  
{  
    int n,i,j,q,a,b;  
    cin>>n;  
    for(i=1;i<=n;i++)  
        for(j=1;j<=n;j++)  
        {  
            cin>>s[i][j];  
            if(!s[i][j])s[i][j]=Max;  
        }  
    cin>>q;  
    memset(flag,0,sizeof(flag));  
    for(i=0;i<q;i++)  
    {  
        cin>>a>>b;  
        s[a][b]=s[b][a]=0;  
    }  
    cout<<prim(n)<<endl;  
    return 0;  
}  

#include<iostream>
using namespace std;
#define N 105
#define Max 0x7ffff
int s[N][N],dist[N],flag[N];
int minn(int a,int b)
{
	return a<b?a:b;
}
void print(int n)
{
	int i;
	for(i=1;i<=n;i++)cout<<dist[i]<<" ";
	cout<<endl;
	for(i=1;i<=n;i++)cout<<flag[i]<<" ";
	cout<<endl;
}
int prim(int n)
{
	int now,t,i,min,sum=0,minx;
	for(i=1;i<=n;i++)dist[i]=s[1][i];
	flag[1]=1;
	for(t=1;t<n;t++)
	{
		minx=Max;
		for(i=1;i<=n;i++)if(!flag[i]&&minx>dist[i])
		{
			min=i;
			minx=dist[i];
		}
		sum+=dist[min];
		flag[min]=1;
		now=min;
		for(i=1;i<=n;i++)
			if(!flag[i]&&dist[i]>s[now][i])dist[i]=s[now][i];
	}
	return sum;
	

}
int main()
{
	int n,i,j,q,a,b;
	cin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			cin>>s[i][j];
			if(!s[i][j])s[i][j]=Max;
		}
	cin>>q;
	memset(flag,0,sizeof(flag));
	for(i=0;i<q;i++)
	{
		cin>>a>>b;
		s[a][b]=s[b][a]=0;
	}
	cout<<prim(n)<<endl;
	return 0;
}