AcWing920 最优乘车(最短路)

这题建图比较清晰,就是把能走到的权值设为1

AcWing920 最优乘车(最短路)
#include<iostream>
#include<sstream>
#include<cstring>
#include<queue>
using namespace std;
const int N=510;
int g[N][N];
int d[N];
bool st[N];
int stop[N];
int n,m;
void bfs(){
    memset(d,0x3f,sizeof d);
    queue<int> q;
    q.push(1);
    d[1]=0;
    int i;
    while(q.size()){
        int t=q.front();
        q.pop();
        for(i=1;i<=n;i++){
            if(g[t][i]&&d[i]>d[t]+1){
                d[i]=d[t]+1;
                q.push(i); 
            }
        }
    }
}
int main(){
    cin>>m>>n;
    string s;
    getline(cin,s);
    while(m--){
        int cnt=0,p;
        getline(cin,s);
        stringstream ssin(s);
        while(ssin>>p){
            stop[cnt++]=p;
        }
        int i,j;
        for(i=0;i<cnt;i++){
            for(j=i+1;j<cnt;j++){
                g[stop[i]][stop[j]]=1;       
            }
        }
    }
    bfs();
    if(d[n]==0x3f3f3f3f)
    cout<<"NO"<<endl;
    else
    cout<<d[n]-1<<endl;
}
View Code

 

AcWing920 最优乘车(最短路)

上一篇:linux(不会考特别难,牢记下面即可)


下一篇:使用Swagger为ASP.NET Core WebApi生成API文档