【模板】单源最短路1

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
//这题使用邻接图过于浪费空间了，所以采用邻接表来存储无向关系
//不管使用邻接表还是邻接图都出现了只有13组用例通过的情况，那这可以确定应该是基本逻辑没有问题，但是边界的处理上还是存在漏洞才会这个样子



//----当输入部分从while（scanf()!=EOF）改为了while(m--)以后就成功通过了
//推测很有可能是因为部分案例不是以EOF结尾的或者说给出的边的数量超过了m，通过控制m以后控制了输入的数量。避免了m条边后面的信息被录入进来干扰了代码。提高了代码的健壮性
#define MAXNUM 5009
typedef struct ArcNode {
    struct VNode* firstvnode;   //顶点链接的第一条边
} arcnode, arcnodelist[MAXNUM];

typedef struct VNode {
    int othervec;   //另一节点
    struct VNode* nextvnode;    //下一条边
} vnode;

typedef struct GRAPH {
    arcnodelist list;
    int n, m;
} graph;            //邻接表信息

typedef struct FIND {
    int val;
    int address;
} Find[MAXNUM];

void buildGraph(int n, int m, graph* G); //创建邻接表
int BFSfind(int n, int now, int findnum, Find find, bool* visited, graph* G);
//广度优先搜索

int main() {
    int n, m;
    scanf("%d %d ", &n, &m);
    graph* G = (graph*)malloc(sizeof(graph));
    G->n = n;
    G->m = m;
    for (int i = 0; i < MAXNUM; i++) {
        G->list[i].firstvnode = NULL;
    }
    int a,b;
    while (m--)
    {
        scanf("%d %d", &a, &b);
        buildGraph(a, b, G);
    }

//----------------初始化邻接表-----------------
    bool visited[MAXNUM] = {0};
    Find find;
    int now, findnum;
    find[0].val = 1;
    find[0].address = 0;
    findnum = 1;
    now = 0;
    visited[1] = true;
    printf("%d", BFSfind(G->n, now, findnum, find, visited, G));
    return 0;
}

int BFSfind(int n, int now, int findnum, Find find, bool* visited, graph* G) {
    while(now<findnum)
    {
        vnode* tmp = G->list[find[now].val].firstvnode;
        while (tmp != NULL) {
        if (visited[tmp->othervec] == 0) {
            visited[tmp->othervec] = true;
            find[findnum].val = tmp->othervec;
            find[findnum].address = find[now].address + 1;
            if (find[findnum].val == n)
                return find[findnum].address;
            findnum++;
        }
        tmp = tmp->nextvnode;
        }
        free(tmp);
        now++;
    }
    return -1; 
}
//这里在创建邻接表的时候，不需要把新的边的关系连在链表的后面，直接加载最开始的部分会更加容易，也省去了很多判断和循环
void buildGraph(int n, int m, graph* G) {  
    vnode* newNode = (vnode*)malloc(sizeof(vnode));  
    newNode->othervec = m;  
    newNode->nextvnode = G->list[n].firstvnode;  
    G->list[n].firstvnode = newNode;  
  
    vnode* newNodeM = (vnode*)malloc(sizeof(vnode));  
    newNodeM->othervec = n;  
    newNodeM->nextvnode = G->list[m].firstvnode;  
    G->list[m].firstvnode = newNodeM;  
}