链式前向星——最短路

一、遍历所有边

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100501
struct Node {
	int val;
	int to;
	int next;//next[i]表示与第i条边同起点的上一条边的储存位置
} node[MAXN];
int cnt = 0;
int head[MAXN]; 
void add(int u, int v, int val) {
	node[cnt].val = val;
	node[cnt].to = v;//node[i]表示第i条边的终点 
	node[cnt].next = head[u];//head[i]表示以i为起点的最后一条边的储存位置 
	head[u] = cnt++;
}
int main() {
	memset(head, 0, sizeof(head));
	cnt = 1;
	int n, m;
	cin >> n >> m;
	int a, b, c;
	for(int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c); 
	}
	for(int i = 1; i <= n; i++) {
		cout << i << ":" << endl;
		for(int j = head[i]; j != 0; j = node[j].next)
		cout << " -> " << node[j].to << " " << node[j].val << endl; 
	}
	return 0;
}

二、求最短路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int dis[maxn];
const int inf = 0x7fffffff;
struct Tree {
	int next;//用来存储相同开始点的下一条边的编号
	int val;//储存边权 
	int to;//储存开始点能到达的下一个点 
}node[maxn];
int n, m;
int head[maxn], cnt = 0;
int inq[maxn];
inline void add(int x, int y, int z) {
	node[++cnt].next = head[x];
	node[cnt].val = z;
	node[cnt].to = y;
	head[x] = cnt;
}
queue <int> q;
void dij(int x) {
	for(int i = 1; i <= n; i++) dis[i] = inf;
	dis[x] = 0;
	q.push(x);
	inq[x] = 1;
	while(q.empty() == false) {
		int now = q.front();
		q.pop();
		inq[now] = 0;
		for(int i = head[now]; i; i = node[i].next) {
			int y = node[i].to;
			int v = node[i].val;
			//cout << now << " " << y << " " << v << endl;
			if(dis[now] + v < dis[y]) {
				dis[y] = dis[now] + v;
				if(inq[y] == 0) {
					q.push(y);
					inq[y] = 1;
				}
			}
		}
	}
}
int main() {
	cin >> n >> m; 
	for(int i = 1; i <= m; i++) {
		int x, y, z; 
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z);
	}
	dij(1);
	for(int i = 1; i <= n; i++) cout << dis[i] << endl;
	return 0;
} 
/*
5 6
1 2 3
2 3 4
3 5 1
4 5 1
2 4 8
1 4 10
*/

三、求最短路数量

P1144 最短路计数

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int dis[maxn];
const int inf = 0x7fffffff;
struct Tree {
    int next;//用来存储相同开始点的下一条边的编号
    int val;//储存边权 
    int to;//储存开始点能到达的下一个点 
}node[maxn];
int n, m;
int head[maxn], cnt = 0;
int inq[maxn];
int ans[maxn]; 
inline void add(int x, int y, int z) {
    node[++cnt].next = head[x];
    node[cnt].val = z;
    node[cnt].to = y;
    head[x] = cnt;
}
queue <int> q;
void dij(int x) {
    for(int i = 1; i <= n; i++) dis[i] = inf;
    dis[x] = 0;
    q.push(x);
    inq[x] = 1;
    ans[x] = 1;
    while(q.empty() == false) {
        int now = q.front();
        q.pop();
        inq[now] = 0;
        for(int i = head[now]; i; i = node[i].next) {
            int y = node[i].to;
            int v = node[i].val;
            if(dis[now] + v < dis[y]) {
                dis[y] = dis[now] + v;
                if(inq[y] == 0) {
                    q.push(y);
                    inq[y] = 1;
                }
                ans[y] = ans[now];
            }
            else if(dis[now] + v == dis[y]) {
            	ans[y] = (ans[now] + ans[y]) % 100003;
			}
        }
    }
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
    cin >> n >> m; 
    for(int i = 1; i <= m; i++) {
        int x, y, z; 
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    dij(1);
    for(int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
} 
/*
5 7
1 2 1
1 3 1
2 4 1
3 4 1
2 3 1
4 5 1
4 5 1
*/

四、输出最短路

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1e3 + 10;
const int inf = 0x7fffffff;
struct Node {
	int next, to, val;
}node[maxn];
int head[maxn], cnt = 0;
void add(int x, int y, int z) {
	node[++cnt].next = head[x];
	node[cnt].to = y;
	node[cnt].val = z;
	head[x] = cnt;
}
int dis[maxn], pre[maxn], inq[maxn];
void dij(int x) {
	queue <int> q;
	for(int i = 1; i <= n; i++) dis[i] = inf;
	dis[x] = 0;
	inq[x] = 1;
	q.push(x);
	while(q.empty() == false) {
		int now = q.front();
		q.pop();
		inq[now] = 0;
		for(int i = head[now]; i; i = node[i].next) {
			int y = node[i].to;
			int v = node[i].val;
			if(dis[y] > dis[now] + v) {
				dis[y] = dis[now] + v;
				pre[now] = y;
				if(inq[y] == 0) {
					inq[y] = 1;
					q.push(y);
				}
			}
		}
	} 
}
void print_path() {
	queue <int> path;
	int now = 1;
	while(1) {
		path.push(now);
		if(now == n) break;
		now = pre[now];
	}
	while(path.empty() == false) {
		int ans = path.front();
		path.pop();
		cout << ans << " ";
	}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z); 
	}
	dij(1); 
	cout << dis[n] << endl;
	print_path();
	return 0; 
}
/*
5 7
1 2 2
1 3 3
3 4 2
4 5 2
2 5 3
2 3 2
2 4 3
*/

五、简单判环

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int dis[maxn];
const int inf = 0x7fffffff;
struct Tree {
	int next;
	int val; 
	int to;
}node[maxn];
int n, m;
int head[maxn], cnt = 0;
int inq[maxn], num[maxn];
inline void add(int x, int y, int z) {
	node[++cnt].next = head[x];
	node[cnt].val = z;
	node[cnt].to = y;
	head[x] = cnt;
}
queue <int> q;
bool dij(int x) {
	for(int i = 1; i <= n; i++) dis[i] = inf;
	dis[x] = 0;
	q.push(x);
	inq[x] = 1;
	while(q.empty() == false) {
		int now = q.front();
		q.pop();
		inq[now] = 0;
		for(int i = head[now]; i; i = node[i].next) {
			int y = node[i].to;
			int v = node[i].val;
			if(dis[now] + v < dis[y]) {
				dis[y] = dis[now] + v;
				if(inq[y] == 0) {
					q.push(y);
					inq[y] = 1;
				}	
				num[y]++;
				if(num[y] > n) return false;
			}
		}
	}
	return true;
}
int main() {
	cin >> n >> m; 
	for(int i = 1; i <= m; i++) {
		int x, y, z; 
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z);
	}
	if(dij(1) == false) cout << "有环";
	else cout << dis[n] << endl; 
	return 0;
} 
/*
5 6
1 2 3
2 3 4
3 5 1
4 5 1
2 4 8
1 4 10
*/