【模板】单源最短路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))

#include<bits/stdc++.h>
using namespace std;
typedef struct{
    int id;
    int sum;
}node;
int g[5001][5001];
bool vis[5001];
queue<node>q;
void bfs(int s,int e){
    node first;
    first.id=s;
    first.sum=0;
    q.push(first);
    vis[s]=true;
    while(!q.empty()){
        node node1=q.front();
        if(node1.id==e){
            cout<<node1.sum;
            break;
        }
        q.pop();
        for(int i=1;i<=5000;i++){
            if(vis[i]==false&&g[node1.id][i]!=0){
                node it;
                it.id=i;
                it.sum=node1.sum+1;
                q.push(it);
                vis[i]=true;
            }
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        g[x][y]=g[y][x]=1;

    }
    bfs(1,n);
    if(q.front().id!=n)
    cout<<-1;
    return 0;
    
}

#include<iostream>
#include <queue>
#include<vector>
#include<climits>

using namespace std;

// 以下是spfa的实现
void SPFA(int Node_n, vector<int>& distance, const vector<vector<int>>& graph){
    queue<int> Qgraph;
    vector<bool> NodeState(Node_n + 1, false);
    
    Qgraph.push(1);  // 先第一个点入队
    distance[1] = 0; // 第一点到第一点的距离为0
    NodeState[1] = true; // 标记第一点入队
    while(!Qgraph.empty()){
        int Node = Qgraph.front();
        Qgraph.pop();
        NodeState[Node] = false;
        for(int i = 1; i <= graph[Node].size(); i++){ // 更新维护路径距离表
             if(graph[Node][i] != INT_MAX  && distance[i] > distance[Node] + graph[Node][i]){
                distance[i] = distance[Node] + graph[Node][i];
                if(!NodeState[i]){
                    Qgraph.push(i);
                    NodeState[i] = true;
                }
             }
        }
    }

}

int main(){
    int Node_n = 10, Edge_m = 10;
    cin >> Node_n >> Edge_m;
    // 先把图存起来
    vector<vector<int>> graph(2*Edge_m, vector<int>(2*Edge_m, INT_MAX));
    // 查了半天，请记得vector的嵌套用法，谢谢你。
    vector<int> distance(Edge_m+1, INT_MAX);
    while(Edge_m--){
        int u = 0, v = 0;
        cin >> u >> v;
        graph[u][v] = 1;  // 邻接表，表示u到v的距离为1
        graph[v][u] = 1; // 注意为无向图，需要关于主对角线对称，因此两边都需要存储相等值
    }
    SPFA(Node_n, distance, graph);
    if(distance[Node_n] != INT_MAX){
        cout << distance[Node_n] << endl;
    }else {
        cout << -1 << endl;
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX 5001

int** new_map(int n){
    int** res=(int**)malloc((n+1)*sizeof(int*));
    for(int i=0;i<=n;i++){
        res[i]=(int*)malloc((n+1)*sizeof(int));
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            res[i][j]=-1;
        }
    }
    return res;
}

int main() {
    int n, m;
    scanf("%d %d",&n,&m);
    int** map=new_map(MAX);
    for (int i=0; i<m ; i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        map[u][v]=1;
        map[v][u]=1;
    }

    //初始化队列
    int* queue=(int*)calloc(MAX, sizeof(int));
    int head=0,tail=0;
    //初始化访问数组,0未访问，1已访问
    int* visited=(int*)calloc(MAX, sizeof(int));
    //初始化计数数组
    int* count=(int*)calloc(MAX, sizeof(int));

    int size=n+1;
    //1号节点入队
    queue[tail]=1;
    tail=(tail+1)%size;
    visited[1]=1;
    count[1]=0;
    //当队列不为空时
    while (head!=tail) {
        //出队一个元素
        int p=queue[head];
        head=(head+1)%size;
        //遍历p能到达的所有未被访问的点
        for(int i=1;i<MAX;i++){
            if(visited[i]==0 && map[p][i]!=-1){
                //i入队，并标记为访问过
                queue[tail]=i;
                tail=(tail+1)%size;
                visited[i]=1;
                //更新i对应计数
                count[i]=count[p]+1;
            }
        }
    }

    if(visited[n]==0){
        printf("-1");
    }else {
        printf("%d",count[n]);
    }

    return 0;
}