基础最短路模板:
有 n 个人,他们的编号为 1~n,其中有一些人相互认识,现在 x 想要认识 y,可以通过他所认识的人来认识更多的人
(如果 x 认识 y、y 认识 z,那么 x 可以通过 y 来认识 z),求出 x 最少需要通过多少人才能认识 y。
【输入格式】
第 1 行 3 个整数 n、x、y,n≤100,1≤x、y≤n。
接下来是一个 n×n 的邻接矩阵,a[i][j]=1 表示 i 认识 j,a[i][j]=0 表示不认识。
保证 i=j 时,a[i][j]=0,并且 a[i][j]=a[j][i]。
【输出格式】
输出一行一个数,表示 x 认识 y 最少需要通过的人数。
【样例输入】
5 1 5
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
0 0 0 1 0
【样例输出】
2
#include<bits/stdc++.h>
using namespace std;
/*
1.可以直接跑BFS
2.无向图最短路径,因为只有输入只有一次查询,那么dijkstra,spfa都可以
dijkstart:因为权值全都为1,所以就不用考虑堆优化.
3.还有一种多源不含负权最短路径,floyd 算法,时间复杂度0(n^3),填空题可以使用一下
借用的是动态规划的思路
*/
int u[105][105];
int n,X,Y;
int bfs(){
queue<pair<int,int>>que;//先进先出,对于每一个条路线需要记录所走的路径长度
vector<int>judg(n+1,0);//标记数组
que.push({X,0});
while(!que.empty()){
pair<int,int> k=que.front();
que.pop();
if(k.first==Y){
return k.second-1;//访问到时走的路程-1就是访问的人数
}
if(judg[k.first])continue;//标记点,防止反复访问同一个点
judg[k.first]=1;
for(int i=1;i<=n;i++){
if(i!=k.first&&u[k.first][i]==1){
if(!judg[i]){
que.push({i,k.second+1});
}
}
}
}
return 0;
}
//单源最短路径,不含负权
int dijkstra(int x){
/*
在权值不同的时候,每次取队首的元素,优化到保证是里面最小的,需要把队列改成优先队列
*/
vector<int>ans(n+1,INT_MAX/2);//ans[i]记录x到i的距离
vector<int>judg(n+1,0);//标记数组,保证点只被访问一次
queue<int>que;
que.push(x);
ans[x]=0;
while(!que.empty()){
int k=que.front();
que.pop();
if(judg[k])continue;//被标记过
judg[k]=1;
for(int i=1;i<=n;i++){
//if 保证不是自己到自己 k->i存在边
if(k!=i&&u[k][i]==1&&ans[i]>ans[k]+1){//更新距离,如果x->i的距离大于x->k->i,就跟新
ans[i]=ans[k]+1;
if(!judg[i]){ //满足没有被访问过,加入队列
que.push(i);
}
}
}
}
return ans[Y]-1;//
}
//包含负权,特判是否存在负环
int spfa(int x){
vector<int>ans(n+1,INT_MAX/2);//ans[i]记录x到i的距离,类似于dijkstra
vector<int>judg(n+1,0);//标记数组,保证队列内不存在重复的点
vector<int>e(n+1,0); //特判数组,表示每个点入栈多少次,如果超过总点数就说明存在负环,一直循环
queue<int>que;
que.push(x);//进队
ans[x]=0;
e[x]++;
while(!que.empty()){
int k=que.front();
que.pop();
if(e[k]>n)return false;//存在负环,找不到答案
judg[k]=false;//不存队列中了
for(int i=1;i<=n;i++){
if(k!=i&&u[k][i]==1&&ans[i]>ans[k]+1){
ans[i]=ans[k]+1;
if(!judg[i]){ //不存在队列,加入
judg[i]=true;
e[i]++;
que.push(i);
}
}
}
}
return ans[Y]-1;
}
//多源最短路径
int floyd(int x,int y){
vector<vector<int>>ans(n+1,vector<int>(n+1,INT_MAX/2));//ans[i][j]表示i->j的距离
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(u[i][j]){
ans[i][j]=1;//所有的距离都是1
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(ans[i][j]>ans[i][k]+ans[k][j]){
ans[i][j]=ans[i][k]+ans[k][j];
}
}
}
}
return ans[x][y]-1;
}
int main(){
scanf("%d%d%d",&n,&X,&Y);
//编号从1开始,那么所有的都按1
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&u[i][j]);
}
}
// printf("%d",bfs());
// printf("%d",dijkstra(X));//求x->到所有的距离
// printf("%d",spfa(X)); //求x->到所有的距离
printf("%d",floyd(X,Y)); //x->y的距离
return 0;
}