P5767 [NOI1997]最优乘车 题解
Post time: 2020-02-01 18:37:49
题目链接Link
一道简单图论题，主要难点在于建图。
我们把同一条线路上的所有车站之间全部连一条边，这样就可以直接利用bfs求得最短距离，因为bfs只要到达终点就一定是最短的。
点击查看代码
#include
#include
#include
#include
using namespace std;
const int N=500+21;
int g[N][N],a[N];//因为数据范围较小所以可以直接使用邻接矩阵
struct node{int u,dep;}q[N];
bool vis[N];
int n,m;
int bfs(int s){
memset(vis,0,sizeof(vis));//初始化是好习惯
q[0]=(node){s,0};
vis[s]=1;
int head=0,tail=1;//head头指针，tail尾后指针，这样比较好写。
while(head