代码来自学长讲课视频,不得不说看大神的代码就是舒服
普通数组邻接表存图
//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;
}
