POJ 2421 Constructing Roads

题目

输入邻接矩阵

再 输入 已连接的两个点

输出 最短路径

解析

可以将已连接的两个点的原路径长度 置为 0

再用prim算法求解

 #include   
using namespace std;  
#define N 105   
#define Max 0x7ffff   
int s[N][N],dist[N],flag[N];  
int minn(int a,int b)  
{  
    return adist[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>a>>b;  
        s[a][b]=s[b][a]=0;  
    }  
    cout<
using namespace std;
#define N 105
#define Max 0x7ffff
int s[N][N],dist[N],flag[N];
int minn(int a,int b)
{
	return adist[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>a>>b;
		s[a][b]=s[b][a]=0;
	}
	cout<