图论之最短路径（最优乘车）

头一次用彩色的字体，interesting~（要是有表情包就更好了>_<）

scanf的返回值类型为int，值由后面的参数决定，返回值表示成功读入的数据的个数

　　如：scanf("%d%d", &a, &b); 　　如果a和b都被成功读入，那么scanf的返回值就是2 　　如果只有a被成功读入，返回值为1 　　如果a和b都未被成功读入，返回值为0 　　如果遇到错误或遇到end of file，返回值为EOF。

  scanf（“%c”，&c）吸收回车和空格

      

char c; while(1) { scanf("%c",&c); if(c=='\n') break; } cin 会在再次遇到空格或者回车时，结束读入，并不接受回车或者空格scanf("%s",s) 不接受空格回车

 还有一个输入有点麻烦的题（突然想用表情包）

等着我去挖一个来

6666666666

题目传送门

解题思路：这题的思想挺难想（大佬请无视），主要是将同一条路线的两个能够相通的站点距离置为1，

比如 1  5  3   4

那么1 到 5，1 到 3，1 到 4的距离都是1，以此类推。。

最后求最短路径就行

最后知道真相的我，眼泪流下来

比较麻烦的是输入数据，表示很懵逼

用%d 和getchar 来分别处理数字及字符

#include<bits/stdc++.h> using namespace std; int g[600][600]; int dis[600]; int vis[600]; const int inf=0x7f; int main() { int m,n; cin>>m>>n; int a[1000]; char c; for(int i=1;i<=m;i++){ int len=0; while(1){ scanf("%d",&a[++len]); c=getchar(); if(c=='\n') break; }//处理数据 for(int j=1;j<=len;j++){ for(int k=j+1;k<=len;k++){ g[a[j]][a[k]]=1; //相通则赋值为1 } } } //最短路径的模板 memset(dis,inf,sizeof(dis)); dis[1]=0; for(int k=1;k<=n;k++){ int minn=inf,ii=-1; for(int i=1;i<=n;i++){ if(minn>dis[i]&&!vis[i]){ minn=dis[i],ii=i; } } if(ii==-1) break; vis[ii]=1; for(int i=1;i<=n;i++){ if(g[ii][i]&&!vis[i]){ dis[i]=min(dis[i],dis[ii]+g[ii][i]); } } } if(dis[n]>=inf) cout<<"NO"; //这里是>= else cout<<dis[n]-1; return 0; }