1.stringstream的使用 2.使用矩阵表示图的初始化 3.本题是单向边
#include<iostream>
#include<queue>
#include<cstring>
#include<sstream>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int dist[N],res[N];
int n,m;
bool st[N];
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=true;
for(int j=1;j<=n;j++)
if(dist[j]>dist[t]+g[t][j])
dist[j]=dist[t]+g[t][j];
}
return dist[n];
}
int main(){
cin>>m>>n;
memset(g,0x3f,sizeof g);
string line;
getline(cin,line); //读取m n后的换行
while(m--){
getline(cin,line);
stringstream ssin(line);
int cnt=0,p;
while(ssin>>p) res[cnt++]=p;
//同一条航班间加边
for(int i=0;i<cnt;i++){
for(int j=i+1;j<cnt;j++){
int a=res[i],b=res[j];
g[a][b]=1;
}
}
}
int t=dijkstra();
if(t==INF) puts("NO");
else cout<<max(0,t-1);
return 0;
}