题意:题目确定只有20个国家,之间存在边界的话,距离设置为1。前面的19行,首先第i(1-19)行给出一个x,代表x后面跟的国家数,表示第i行和后面的国家之间存在边界,设置为1.第20行给出表示可能征服的起始国和结束国(也就是国家A和国家B之间的最短距离)。
使用Flody算法:
核心算法:
for(int k=1;k<=20;k++){for(int i=1;i<=20;i++){for(int j=1;j<=20;j++){e[i][j]=min(e[i][k]+e[k][j],e[i][j]);}}}
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<iomanip>
#include<vector>
using namespace std;
const int maxx=22;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];int m;
vector<int>vec[maxx];
void init(){for(int i=0;i<=maxx;i++){for(int j=0;j<=maxx;j++){if(i==j){e[i][j]=0;}else{e[i][j]=inf;}}}
}
void Flody(){for(int k=1;k<=20;k++){for(int i=1;i<=20;i++){for(int j=1;j<=20;j++){e[i][j]=min(e[i][k]+e[k][j],e[i][j]);}}}
}
int main(){int count=1;int n;while(scanf("%d",&n)!=EOF){init();for(int j=1;j<=n;j++){int x;cin>>x;e[1][x]=e[x][1]=1;}int t;for(int i=2;i<=19;i++){cin>>t;for(int j=1;j<=t;j++){int x;cin>>x;e[i][x]=e[x][i]=1;}}Flody();cin>>m;cout<<"Test Set #"<<count++<<endl;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;cout<<a<<" to "<<b<<": "<<e[a][b]<<endl;}cout<<endl;} return 0;
}