floyd 读入时有一个坑点
也算是c/c++语法的一个坑点,一不留神,就被坑去好几个小时就找bug
/(ㄒoㄒ)/~~
读取01矩阵的时候,如果点是从1开始标记的时候,cin>>某一个行,或着scanf(“%s”,某一行);就会出错
因为这样的话,指针的初始位置在每一行下标为0的地方
这样写会被坑死
char ppt[N][N];
for(int i=1;i<=n;i++){
scanf("%s",ppt[i]);
//cin>>ppt[i];
}
正确的读入姿势
char ppt[N][N];
for(int i=1;i<=n;i++){
scanf("%s",ppt[i]+1);
//cin>>ppt[i]+1;
}
或者这样
getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
{
scanf("%c",&ppt[i][j]);
}
getchar();
}
AC代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define pdd pair<double,double>
#define F first
#define S second
using namespace std;
const int N=160,INF=0x3f3f3f3f;
pdd gra[N];
char ppt[N][N];
double mmp[N][N];
double maxDist[N];
double get_dist(pdd p1,pdd p2){
return sqrt(pow(p1.F-p2.F,2)+pow(p1.S-p2.S,2));
}
int n;
/* N 牧区数目
* x,y 牧区坐标
* 01矩阵,牧区连通性
* 先利用01建立边权初始关系
* */
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>gra[i].first>>gra[i].second;
}
getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
{
scanf("%c",&ppt[i][j]);
}
getchar();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){mmp[i][j]=0;continue;}
if(ppt[i][j]=='0')mmp[i][j]=INF;//9个0
else if(ppt[i][j]='1')mmp[i][j]=get_dist(gra[i],gra[j]);
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mmp[i][j]>mmp[i][k]+mmp[k][j])
mmp[i][j]=mmp[i][k]+mmp[k][j];
}
}
}
double res1=0,res2=INF;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){//对每一个i统计 距离最远的点
if(mmp[i][j]<INF/2)
maxDist[i]=max(maxDist[i],mmp[i][j]);
}
res1=max(res1,maxDist[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mmp[i][j]>=INF/2){
res2=min(res2,maxDist[i]+maxDist[j]+get_dist(gra[i],gra[j]));
}
}
}
printf("%.6lf",max(res1,res2));
return 0;
}