【模板】单源最短路1

大佬们，跟gpt学的，提交后显示第13个测试用例结果错了。但是我没看出问题在哪，有没有人指点一下

from collections import deque, defaultdict
import sys
def shortest_path(n, edges):
    graph = defaultdict(list)
    for u,v in edges:
        graph[u].append(v)
        graph[v].append(u)
    queue = deque([1])
    distances = {1:0}
    while queue:
        cur = queue.popleft()
        for neighbor in graph[cur]:
            if neighbor not in distances:
                distances[neighbor] = distances[cur] + 1
                queue.append(neighbor)
            if neighbor == n:
                print(distances[neighbor])
                return
    print(-1)
edges = []
n,m = input().split()
for line in sys.stdin:
    u,v = line.split()
    edges.append( (int(u), int(v)) )
shortest_path(int(n), edges)

#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n = 0, m = 0, u = 0, v = 0;
    cin >> n >> m;
    n--;
    vector<queue<int>> table(5000, queue<int>());
    vector<int> dist(5000, INT_MAX);
    vector<int> flag(5000, 0);
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--;
        v--;
        table[u].push(v);
        table[v].push(u);
        if (!u) {
            dist[v] = 1;
            flag[v] = 1;
        }
        if (!v) {
            dist[u] = 1;
            flag[u] = 1;
        }
    }
    dist[0] = 0;
    flag[0] = 1;
    int k = 5000;
    if (k > m) k = m;
    while (k--&&!flag[n]) {
        for (int i = 1; i < 5000; i++) {
            if (flag[i]) {
                while (!table[i].empty()) {
                    if (dist[i] + 1 < dist[table[i].front()]) dist[table[i].front()] = dist[i] + 1;
                    table[i].pop();
                }
            }
        }
        for (int i = 0; i < 5000; i++) {
            if (dist[i] < INT_MAX) flag[i] = 1;
        }
    }
    if (flag[n]) cout << dist[n] << endl;
    else cout << -1 << endl;
    return 0;
}

import collections 

def bfs_sin(start,target,graph):
    dp = collections.deque()
    v = set()
    dp.append(start)
    res = {start:0}
    while dp:
        u = dp.popleft()
        if u == target:
            return res[target]
        for i in graph[u]:
            if i not in v:
                v.add(i)
                res[i] = res[u] + 1
                dp.append(i)
    return '-1'
            
n,m = map(int,input().split())
graph = collections.defaultdict(list)
for i in range(m):
    u,v = map (int,input().split())
    graph[u].append(v)
    graph[v].append(u)
print(bfs_sin(1,n,graph))

#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;  
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;
const int MAXN = 5000;
const int INF = 1e8;
vector<int> graph[MAXN];
bool visited[MAXN] = {false};
int d[MAXN];
void dijkstra(int n, int start) {
    for (int i = 0; i < MAXN; i++)d[i] = INF;
    d[start] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        int MIN = INF;
        for (int j = 0; j < n; j++) {
            if (d[j] < MIN && !visited[j]) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1)return;
        visited[u] = true;
        for (int j = 0; j < graph[u].size(); j++) {
            int v = graph[u][j];
            if (!visited[v] && d[u] + 1 < d[v]) {
                d[v] = d[u] + 1;
            }
        }
    }

}
int main() {
    cin >> n >> m;
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        graph[u - 1].push_back(v - 1);
        graph[v - 1].push_back(u - 1);
    }
    dijkstra(n, 0);
    if (d[n - 1] == INF) {
        cout << -1;
    } else
        cout << d[n - 1];
}

from collections import deque

def sol(mp, n):
    Q = deque()
    visited = {} #记录访问过的点
    res = 0
    Q.append(0)
    while Q:
        res += 1
        size = len(Q)
        for _ in range(size):
            id = Q.popleft()
            for j in range(len(mp[id])):
                if mp[id][j] == n - 1:
                    return res
                if mp[id][j] not in visited:
                    Q.append(mp[id][j])
                    visited[mp[id][j]] = 1
    return -1


n, m = map(int, input().split())
mp = [[] for _ in range(2 * n)] #邻接矩阵，预留了较大的空间
for _ in range(m):
    x1, x2 = map(int, input().split())
    mp[x1 - 1].append(x2 - 1)
    mp[x2 - 1].append(x1 - 1)
print(sol(mp, n))