存图
vector
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 100;
struct Edge{
int to,value;
}e;
vector<Edge> G[N+1];
int m,n,tmp;
int main(){
cin>>n>>m;
for (int i=0;i<m;i++){
cin>>tmp>>e.to>>e.value;
G[tmp].push_back(e);
}
for (int i=1;i<=n;i++){
for (int j=0;j<G[i].size();j++){
e=G[i][j];
cout<<"From "<<i<<" to "<<e.to<<", the cost is "<<e.value<<endl;
}
}
return 0;
}
链式前向星（常用）
这个主要是模拟链表
对于每一个节点：
对于每条边记录指向的点x，边权w，该边的编号，下一条边的编号nxt
为了存边的方便，我们对其进行了如下改进：nxt记录这条边前一条边编号，head[i]记录最后一个边的编号
struct Edge{
int nxt,to,w;
}e[100001];
int a[1000001] = { };
int head[1000001],ecnt = 0;
void addEdge(int x,int y,int w){
++ecnt;
e[ecnt].nxt = head[x];
e[ecnt].to = y;
e[ecnt].w = w;
head[x] = ecnt;
}
最短路
单源最短路
DIJ
我们默认他的起点是1号点（这是可以自己改的）
算法流程：
初始化dis[1] = 0，其他节点：dis[i] = INF(很大)；
在没标记的节点中，找一个dis[x]最小的节点x,并将其标记
扫描出边（x,y,z）若dis[y] > dis[x] + z。则用dis[x] + z更新dis[y]
但是很显然，这样做的时间复杂度是很高的，所以我们需要一点优化，用优先队列存维护，这样每次直接把最小值取出来然后删除就行了
#include<cstring>
#include<cstdio>
#include<queue>
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int> pr;//定义一个pair，pr替pair
struct Edge{
int nxt,to,w;
}e[3000001];
struct cmp
{
bool operator()(const pr p1,const pr p2)
{
return p1.second < p2.second;
}
};//重载运算符，背住
int n,m,s;
int head[3000001];
int ecnt = 0;
int dis[3000001] = { };
priority_queue<pr, vector<pr>, greater<pr> > q;//优先队列
void addEdge(int x,int y,int w){
++ecnt;
e[ecnt].nxt = head[x];
e[ecnt].w = w;
e[ecnt].to = y;
head[x] = ecnt;
}//存图
int vis[3000001] = { };
void dijkstra()
{
memset(dis, 0x3f,sizeof(dis));
dis[s] = 0;
q.push(make_pair(0, s)); //0是距离，出发点到出发点距离是0，s是出发点
while(!q.empty())
{
int now = q.top().second; //now存的是现在点的位置
q.pop();
if(vis[now]) continue;
vis[now] = 1;//标记
for(int i = head[now]; ~i; i = e[i].nxt)//遍历
{
int v = e[i].to;
if(dis[v] > dis[now] + e[i].w)
{
dis[v] = dis[now] + e[i].w;
q.push(make_pair(dis[v], v));
}
}
}
}
int main(){
scanf("%d %d %d" ,&n,&m,&s);
memset(head,-1,sizeof(head));
for(int i = 1;i <= m; i++){
int a,b,c;
scanf("%d %d %d" ,&a,&b,&c);
addEdge(a,b,c);
}
dijkstra();
for(int i = 1;i <= n; i++){
printf("%d " ,dis[i]); //输出到每个点的距离
}
return 0;
}
注意dij的局限性：不能用于负边权的边
SPFA
这个其实是用队列优化的Bellman-Ford算法
那么什么事Bellman_Ford算法呢？
简而言之 ：给你一个有向图，有一条边（x,y,z），若dis[y] <= dis[x]+z，则该边满足三角不等式，当所有边都满足三角不等式，dis[ ]即为所求
算法的基本流程如下：
队列，初始只有1。
取出对头x，扫描出边（x,y,z）若dis[y] > dis[x] + z,则用dis[x] + z更新dis[y],若y不在队列中，y入队
In void spfa()
{
Mem(dis, 0x3f), dis[1] = 0;
q.push(1);
while(!q.empty())
{
int now = q.front(); q.pop();
vis[now] = 0;
for(int i = head[now]; ~i; i = e[i].nxt)
{
int v = e[i].to;
if(dis[v] > dis[now] + e[i].w)
{
dis[v] = dis[now] + e[i].w;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
SPFA判负环：
#include <bits/stdc++.h>
using namespace std;
inline int gin() {
char c = getchar();
int s = 0, f = 1;
while (c < ‘0‘ || c > ‘9‘) {
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0‘ && c <= ‘9‘) {
s = (s << 3) + (s << 1) + (c ^ 48);
c = getchar();
}
return s * f;
}
const int N = 5e3 + 5;
int n, m, cnt[N], d[N], tot = 0, head[N];
bool h[N], t;
queue<int> q;
struct edge {
int dis, ne, to;
} e[N << 1];
inline void add(int u, int v, int w) {
e[++tot].dis = w;
e[tot].to = v;
e[tot].ne = head[u];
head[u] = tot;
}
inline void spfa() {
memset(h, 0, sizeof h);
memset(cnt, 0, sizeof cnt);
memset(d, 63, sizeof d);
h[1] = 1, t = 0, d[1] = 0;
q.push(1);
while (q.size()) {
int u = q.front();
q.pop();
h[u] = 0;
if (cnt[u] == n - 1) {
t = 1;
return;
}
cnt[u]++;
for (int i = head[u]; i; i = e[i].ne) {
int v = e[i].to, w = e[i].dis;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (!h[v])
h[v] = 1, q.push(v);
}
}
}
}
int main() {
int T = gin();
while (T--) {
n = gin(), m = gin();
tot = 0;
memset(head, -1, sizeof head);
for (int i = 1; i <= m; i++) {
int u = gin(), v = gin(), w = gin();
add(u, v, w);
if (w >= 0)
add(v, u, w);
}
spfa();
if (t)
printf("YE5\n");
else
printf("N0\n");
}
return 0;
}
拓扑排序
将一个有向无环图所有节点转换成一个线性序列，是所有能走到v的点都排在v的前面
算法的思路：我们令du[i]表示入度，然后——
1、入度为0的，放入队列
2、取出队首u,把u到v所有边du[v] - 1
3、若du[v]=0，v出队
4、重复上述步骤
void topo_sort(){
queue<int>q;
for(int i = 1;i <= n; i++){
if(!du[i]) q.push(i);
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = head[now];~i;i = e[i].nxt){
int v = d[i].to;
if(!--du[v])q.push(v);
}
}
}
}