邻接表存图 SPFA

代码来自学长讲课视频,不得不说看大神的代码就是舒服

普通数组邻接表存图

//MAXN代表点的最大数量，MAXM代表边的最大数量 
const int MAXN=10000, MAXM=10000;
int head[MAXN];    //存储第x号点链表的头部位置 
int ver[MAXM];    //存储边的终点信息
int edge[MAXM];    //存储边的边权信息
int nextVer[MAXM]; //存储链表中下一个节点的位置
int total;

//初始化 
memset(head, -1, sizeof(head));
total=0;

//加入从x到y的有向边,权值为z
void addEdge(int x, int y, int z){
   
    total++;    //从1开始存 
    ver[total]=y, edge[total]=z;    //边的信息 
    nextVer[total]=head[x], head[x]=total;//插入链表中 
} 

//访问从x出发的所有边
for (int i=head[x]; i!=-1; i=nextVer[i]){
   
    //找到1条从x到y的边,权值为z 
    int y=ver[i], z=edge[i];
}

vector邻接表存图

const int MAXN=10000, MAXM=10000;
//可以将vector看成一列的形式，对应于一列head。
//每个元素都是一个pair<int, int>类型。表示终点和权值 
vector<pair<int, int>> e[MAXM];

//初始化
for (int i=0; i<MAXN; i++)
    e[i].clear(); 

//添加从x到y边权为z的边信息
//这个就是尾插法插进链表。
//要知道邻接表里每个头顶点连接的链表中的节点顺序无所谓 
void addEdge(int x, int y, int z){
   
    e[x].push_back(make_pair(y, z));
} 

//访问从x出发的所有边
for (int i=0; i<e[x].size(); i++){
   
    //找到一条从x到y的边权为z的边 
    int y=e[x][i].first;
    int z=e[x][i].second;
}

再帖一个spfa+邻接表存图的代码(感觉全忘光了)
https://blog.csdn.net/weixin_42172261/article/details/95390000

洛谷3371

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int> > edge[50005];
int dis[10005];
int book[10005];
int n, m, s;

void add_edge(int x, int y, int z){
   
    edge[x].push_back(make_pair(y, z));
}
void spfa(){
   
    for (int i=1; i<=n; i++)
        dis[i] = (1<<31) -1;
    dis[s] = 0;
    queue<int> q;
    while (!q.empty())
        q.pop();
    q.push(s);
    book[s] = 1;
    while (!q.empty()){
   
        int t = q.front();
        q.pop();
        book[t] = 0;
        for (int k=0; k<edge[t].size(); k++){
   
            int y=edge[t][k].first;
            int z=edge[t][k].second;
            if (dis[y] > dis[t]+z){
   
                dis[y]=dis[t]+z;
                if (book[y]==0){
   
                    q.push(y);
                    book[y]=1;
                }
            }
        }
    }
}
int main(){
   
    scanf("%d%d%d", &n, &m, &s);
    for (int i=1; i<=m; i++){
   
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add_edge(x, y, z);
    }
    spfa();
    for (int i=1; i<=n; i++)
        printf("%d ", dis[i]);
    return 0;
}