POJ 1612 The Geodetic Set Problem G++ floyd最短路径上的点背

tech2024-06-10  62

#include <iostream> #include <cstdio> #include <string> #include <sstream> #include <cstring> using namespace std; //英语 看博友分析 抄博友程序 floyd 最短路径上的点 背 int g[50][50]; long long f[50][50]; int da[50];//全局变量ac 局部变量re int main() { memset(f,0,sizeof(f)); int inf=0x3f3f3f3f; for(int i=0;i<50;i++) { for(int j=0;j<50;j++) { g[i][j]=inf; } } for(int i=0;i<50;i++) { g[i][i]=0; } int n; cin>>n; getchar(); for(int i=1;i<=n;i++) { string s; getline(cin,s); stringstream iss(s);//抄博友程序 int t; while(iss>>t)//抄博友程序 stringstream使用 背 { g[i][t]=1;//无向图 g[t][i]=1; } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(g[i][j]>(g[i][k]+g[k][j]))//最短路径上的点 { g[i][j]=g[i][k]+g[k][j]; } } } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(g[i][j]==g[i][k]+g[k][j]) { f[i][j]=f[i][j]|(1LL<<(k-1));//抄博友程序 LL } } } } int m; cin>>m; //cout<<m<<endl; getchar(); //int da[50];//re while(m--) { int cnt=0; string s; getline(cin,s); stringstream iss(s); while(iss>>da[cnt++]);//抄博友程序 long long ans=0; for(int i=0;i<cnt;i++) { for(int j=0;j<cnt;j++) { ans|=f[da[i]][da[j]]; } } if(ans==((1LL<<n)-1)) { cout<<"yes"<<endl; }else { cout<<"no"<<endl; } } return 0; }

 

最新回复(0)