我终于写出来了

喂俺个炊饼，马飞唉 ...

题意

求有向图最短路

思路

服了,这种输入点的方式贼恶心!!!

调了两年半,结果败在输入

$bfs$的题

如何记录换成的次数(重点)

• 每一条线路的点都要连这条线路的其他点(注意要有向)

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int edge[510][510];
queue<pair<int,int> >q;//站点，距离
int vis[250000]={0};
int bfs()
{
    q.push({1,0});
    vis[1]=1;
    while(!q.empty())
    {
        int u=q.front().first;
        int dis=q.front().second;
        q.pop();
        if(u==n)//找到点是
            return dis;
        for(int i=1;i<=n;i++)
        {
        	int v=edge[u][i];
            if(v && !vis[i])
            {
            	vis[i]=1;
                q.push({i,dis+1});
            }
		}
    }
    return -1;
}
int nu[250000];
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m+1;i++)
    {
        memset(nu,0,sizeof nu);
        int len=0;
        string s;
        getline(cin,s);
        stringstream strs(s);
        while(strs>>nu[len++]);//恶心的输入
        len--;
        for(int j=0;j<len-1;j++)
        {
            for(int k=j+1;k<len;k++)
            {
                edge[nu[j]][nu[k]]=1;//每一条线路的点都要连这条线路的其他点
            }
        }
    }
    int f=bfs();
    if(f!=-1)//是否到终点
        cout<<f-1;
    else
        cout<<"NO";
    return 0;//完结散花
}