第三章
- 深度优先搜素
2.宽度优先搜索 - 树与图的存储
4.树与图的DFS
5.树与图的BFS
6.拓扑排序
从使用数据结构来看
DFS stack
BFS queue
从使用空间来看
DFS O(H); “不具有最短性”
BFS O(2^h) “最短路”(第一次搜到的距离为最短距离)
1.深度优先搜素
(1)回溯 : 注意恢复现场
(2)剪枝 : 最优型剪枝 可行性剪枝
一个DFS一定对应一个搜索树
最重要的想清楚顺序
1.数字排列
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int path[N], vis[N];
int n;
void dfs(int x)
{
if (x > n) {
for (int i = 1; i <= n; i++)
cout << path[i] << ' ';//输出路径
cout << endl;
return;
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
vis[i] = 1;//标记用过
path[x] = i;//加入路径
dfs(x + 1);//枚举下一个位置
vis[i] = 0;//恢复现场
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
2.n皇后问题
顺序1：枚举每一行的皇后放在什么位置
/ /
/ 正对角线上的元素坐标和相同 dg[x + y];
\\ 反对角线上的元素坐标差相同 由于y - x可能是负数所以加上n
dg[y - x + n];
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 20;
bool pal[N],pg[N],upg[N];
char g[10][10];
void dfs(int x) {
if (x > n)
{
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout << g[i][j];
cout << endl;
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (!pal[i] && !pg[x + i] && !upg[n - i + x])
{
pal[i] = pg[x + i] = upg[n - i + x] = true;
g[x][i] = 'Q';
dfs(x + 1);
pal[i] = pg[x + i] = upg[n - i + x] = false;
g[x][i] = '.';
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = '.';
dfs(1);
system("PAUSE");
return 0;
}
第二种
这种方式是更无脑的搜索
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 20;
char g[N][N];
// 依次表示 行 列 正对角线 负对角线
bool row[N], col[N], pg[N], upg[N];
void dfs(int x, int y, int s) { //枚举行列和已经放皇后的个数
if (y > n) {//注意！ 这个是本题的重点
x++; //当y枚举到超过边界时 要让他指向下一行的第一个元素
y = 1;
}
if (s >= n) {
if (s == n) { //如果放皇后数目正好为n则输出方案
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << g[i][j];
}
cout << endl;
}
cout << endl;
}
return;
}
if (x > n) //如果x超过边界则return
return;
dfs(x, y + 1, s);//当前位置不放皇后
//判断 行 列 正对角线 负对角线
if (!row[x] && !col[y] && !pg[x + y] && !upg[n - x + y])
{
row[x] = col[y] = pg[x + y] = upg[n - x + y] = true;
g[x][y] = 'Q'; //标记
dfs(x, y + 1, s + 1);//这个位置放皇后 枚举下一个位置
row[x] = col[y] = pg[x + y] = upg[n - x + y] = false;
g[x][y] = '.';//恢复现场
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = '.';
dfs(1, 1, 0);
return 0;
}
2.BFS
第一次搜到的一定是最小的（图中边的权重相同）
只有边的权重都为1时求最短路才可以使用BFS
DP是一种特殊的最短路 内部没有环的最短路
基本步骤
初始-> queue
while queue 不空
{
t->队头
拓展t
}
BFS在拓展时也要用vis 进行判断
因为只有BFS第一次搜到的点才是最短距离
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N];
int vis[N][N];
int n, m;
int ans = 0x3f3f3f3f;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int k = 1;
bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
struct node {
int x;
int y;
int sum;
}dia[100];
void bfs(int x,int y,int sum) {
queue<node> q;
node dian;
dian.x = x; dian.y = y; dian.sum = sum;
q.push(dian);
while (!q.empty())
{
int xx = q.front().x;
int yy = q.front().y;
int ss = q.front().sum;
q.pop();
if (xx == n && yy == m) {
cout << ss << endl;
return;
}
for (int i = 0; i < 4; i++) {
int nowx = xx + dx[i];
int nowy = yy + dy[i];
if (check(nowx, nowy) && !vis[nowx][nowy] && a[nowx][nowy] == 0)
{
node dian;
dian.x = nowx; dian.y = nowy; dian.sum = ss + 1;
vis[nowx][nowy] = 1;
q.push(dian);
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
bfs(1,1,0);
system("PAUSE");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#include<unordered_map>
int bfs(string start)
{
queue<string > q;
vector<pair<string, int> > v;
q.push(start);
v
}
int main()
{
string start;
cin >> start;
cout << bfs(start) << endl;
system("PAUSE");
return 0;
}
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int bfs(string state) {
queue<string> q;
unordered_map<string, int> d;
q.push(state);
d[state] = 0;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
string end = "12345678x";
while (q.size())
{
string t = q.front();
q.pop();
if (t == end)return d[t];
int distance = d[t];
int k = t.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) {
swap(t[a * 3 + b], t[k]);
if (!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
swap(t[a * 3 + b], t[k]);
}
}
}
return -1;
}
int main()
{
char s[2];
string state;
for (int i = 0; i < 9; i++)
{
cin >> s;
state+= *s;
}
cout << bfs(state) << endl;
system("PAUSE");
return 0;
}
第三节 图
树和图是怎么存储的
树和图有两种存储方式
树是一种特殊的图,树是无环连通图
图分为有向图和无向图
一、只需要考虑有向图如何存储：
1.邻接矩阵（用的比较少） 比较浪费空间
二维数组 g[a][b] 表示a到b这一条边 g[a][b]的值就是a到b的权重
2.邻接表
为图中的每一个点都开一个单链表 存储这个点可以到达的点，单链表中的顺序无关紧要
插入一条新的边从a到b，找到a所在的链表，从a的头把b插入进去
模板：
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;//图是双向的，a可以到b，b也可以到a，n个点的图最多有2n条边
int n, m;
//h数组表示每个点的链表的头节点，e表示节点的值，ne表示节点的next指针，idx表示当前存储到的位置
int h[N], e[M], ne[M], idx;
void add(int a, int b) {//新建立一条边，将b这个节点插入到a链表头节点的后面
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
//h[a]=idx++
}
int main()
{
memset(h, -1, sizeof(h));//将头节点都指向-1（都指向空节点）
return 0;
}
二、树和图的遍历
1.深度优先遍历
2.宽度优先遍历
都是每个点只遍历一次
模板
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;//图是双向的，a可以到b，b也可以到a，n个点的图最多有2n条边
int n, m;
//h数组表示每个点的链表的头节点，e表示节点的值，ne表示节点的next指针，idx表示当前存储到第几条边
int h[N], e[M], ne[M], idx;
bool vis[N];
void add(int a, int b) {//新建立一条边，将b这个节点插入到a链表头节点的后面
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
//h[a]=idx++
}
//res 当前连通块的最大值
void dfs(int u) {
vis[u] = true;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!vis[j])dfs(j);//一条路走到黑
}
}
int main()
{
memset(h, -1, sizeof(h));//将头节点都指向-1（都指向空节点）
dfs(1);
return 0;
}
最短路径 只遍历一次
/*
图的bfs的应用
求拓扑序：
1、概念
拓扑序列 针对于有向图->对于每条边都是起点在终点的前面
如果存在环 则一定不存在拓扑序
一个有向无环图（拓扑图）一定存在拓扑序列
入度：一个节点有几条边进来
出度: 一个节点有几条边出去
2、 拓扑序列的实现
所有入度为0的点都可以作为一个起点
所有入度为0的点入队
while(q不空){
t=队头
枚举t的所有出边 t->j
删掉t->j (因为t已经在j的前面了)
d[j]– d数组表示为j的入度
if(d[j]==0)
queue <– j
如果j的入度减为0了则j也可以作为一个起点入队
}
图的层次遍历·
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = N * 2;
int n, m;
int h[N], e[M], ne[M], vis[N], idx;
long long ans = 0x3f3f3f3f;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void bfs(int num) {
queue<pair<int,long long> > q;
q.push(make_pair(num,0));
vis[num] = 1;
while (!q.empty())
{
pair<int,int> now = q.front();
q.pop();
for (int i = h[now.first]; i != -1; i = ne[i]) {
int j = e[i];
int foot = now.second + 1;
if (j == n)
{
ans = foot;
return;
}
if (vis[j])
continue;
q.push(make_pair(j,foot));
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
bfs(1);
if (ans = 0x3f3f3f3f)
cout << -1 << endl;
else cout << ans << endl;
system("PAUSE");
return 0;
}
有向图的拓扑排序
/*图的bfs的应用
求拓扑序：
1、概念
拓扑序列 针对于有向图->对于每条边都是起点在终点的前面
如果存在环 则一定不存在拓扑序
一个有向无环图（拓扑图）一定存在拓扑序列
入度：一个节点有几条边进来
出度 : 一个节点有几条边出去
2、 拓扑序列的实现
所有入度为0的点都可以作为一个起点
所有入度为0的点入队
while (q不空) {
t = 队头
枚举t的所有出边 t->j
删掉t->j(因为t已经在j的前面了)
d[j]--d数组表示为j的入度
if (d[j] == 0)
queue < --j
如果j的入度减为0了则j也可以作为一个起点入队
}
一个有向无环图的拓扑序不是唯一的*/
/*
数组模拟队列实现BFS
hh=0，tt=-1 hh代表队头 tt 代表队尾
入队操作 q[++tt]=a；
获取队头操作 t=q[hh++];
判断队列是否为空 while(hh<=tt)
出队操作q[++tt]=j;
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx, d[N], vis[N];
int q[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
{
if (d[i] == 0)
{
q[++tt] = i;
}
}
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (--d[j] == 0)
q[++tt] = j;
}
}
return tt == n - 1;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if (!topsort())
{
cout << -1 << endl;
}
else {
for (int i = 0; i < n; i++)
cout << q[i] << ' ';
cout << endl;
}
return 0;
}
第二节
一、最短路的分类
n 表示点的数量 m表示边的数量
1、单源最短路
求一个点到所有点的最短路
(1) 所有边权都是正数
①朴素的dijkstra算法 O（n^2）
时间复杂度和边数无关 适合稠密图（边数多）
适合边数是n^2级别的情况
②堆优化版的dijkstra算法O(mlogn)
适合边数是n级别的情况（节点多 边数少）
（2）存在负权边
①Bellman-Ford算法 O(nm)
②SPFA O(m) 对Bellman-Ford算法的优化
2、多源最短路
起点和终点都不确定，求任意两个点的最短路
Floyd算法 O(n^3)
二、朴素版Dijkstra
1、初始化距离
dis[1]=0 一号点到起点的距离为0，
dis[i]=+∞ 其余的点到起点的距离为无穷
2、迭代
集合s 当前已经确定最短路的点
循环n次 for i:n
迭代找到不在s中的距离最近的点 t
把t加入到s中
用t更新其他点的距离
更新也循环n次 所以总的时间复杂度是n^2;
（看1号点走到x的距离是否大于从1号点走到t，再从t走到x。如果大于则更新1号点到x点的距离）
3、本算法适合于稠密图 用邻接矩阵来存
注意：无向图和有向图的最短路是没有区别的
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];//邻接矩阵存储稠密有向图
int dis[N]; //表示确定的点的最短距离
bool vis[N];//这个点是否被访问过
int Dijkstra() {
memset(dis, 0x3f, sizeof(dis));//其余点初始化距离为无穷
dis[1] = 0;//起点初始化距离为0
for (int i = 1; i <= n; i++) {//首先要遍历N次每次确定一个节点
int t = -1;
for (int j = 1; j <= n; j++) {//第二个for是找出确定距离的点中的最小的节点
if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
t = j;
}
}
vis[t] = true;
for (int j = 1; j <= n; j++) {//第二个for 根据选中的节点 更新距离
dis[j] = min(dis[j], dis[t] + g[t][j]);
}
}
if (dis[n] == 0x3f3f3f3f)
return -1;
else return dis[n];
}
int main()
{
memset(g, 0x3f, sizeof(g));
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << Dijkstra() << endl;
return 0;
}
三、堆优化版的Dijkstra
为了实现在一堆数中找到最小的数 ->需要用堆实现
1、堆的实现
①手写堆 里面n个数
②优先队列 里面m个数 （复杂度稍微提高）
本算法适合稀疏图->存储方式使用邻接表
注意：用邻接表存储 不需要特殊处理重边
边的权不为1的时候邻接表加边模板
add(int a,int b,in c){
e[idx]=b;
ne[idx]=h[a];
wei[idx]=c;
h[a]=idx++;
}
基本思路
1.首先初始化起点的距离为0 其余点的距离为无穷
2.将起点加入到优先队列中 优先队列维护最小值
3.根据堆顶元素的权值和他能到达的点，更新其他点的距离，将更新距离后的点加入到队列中
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * N;
typedef pair<int, int> PII;
int n, m;
int h[N], e[M], wei[M], ne[M], idx;
bool vis[M];
int dis[N];
void add(int a, int b, int c) {//有权重的加边方式
e[idx] = b;
wei[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int Dijkstra() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;//小根堆 距离小的排在前面
pq.push(make_pair(0, 1));
while (pq.size()) {
PII now = pq.top();
pq.pop(); //直接根据已经知道的点和这个点到其他点的权重更新能到达的点的距离
int distance = now.first;
int ser = now.second;
if (vis[ser]) //如果这个点已经加入堆中过了 那么剩下的是冗余的 不可能是最短路
continue;
vis[ser] = true;
for (int i = h[ser]; i != -1; i = ne[i]) {
int j = e[i]; //j代表a->b的b 即ser能到达的点
if (dis[j] > dis[ser] + wei[i]) {
dis[j] = dis[ser] + wei[i];//当前的值可能是无穷 如果当前的值大于从ser点到它的值则更新
//这里的dis[ser]和distance是相等的
pq.push(make_pair(dis[j], j));//将其入队
}
}
}
if (dis[n] == 0x3f3f3f3f)
return -1;
else return dis[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << Dijkstra() << endl;
//system("PAUSE");
return 0;
}
四、Bellman-Ford 算法
适合存在负权的边
具有负环的图 不存在最短路 最短路为负无穷
除非负环不在最短路的途中
如果使用SPFA算法 则要求一定不存在负环
核心操作：
1、迭代n次 for n次
意义：迭代k次 表示经过1号点走过不超过k条边的最短距离
如果迭代n次的时候 还有更新 说明存在负环
2、for 所有边 遍历所有边 m
a b w dis[b]=min(dis[b],dis[a]+w[i]);
(松弛操作)
3、在遍历了n次之后保证了
dis[b]<=dis[a]+w;(三角不等式)
时间复杂度 O(n*m);
SPFA 算法的各方面性能都优于Bellman-Ford算法
但是有边数限制的题（从1号点到n号点最多经过不超过k条边的最短路）只能用Bellman-Ford算法
只要没有负环，就可以用SPFA，绝大多数的最短路问题不存在负环
Bellman-Ford算法限制很少，不需要用邻接矩阵或者邻接表存储，可以直接用结构体存储
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 2 * N;
int n, m,k;
int dis[N], backup[N];
struct Bellman {
int a;
int b;
int c;
Bellman() { //无参构造寒素
a = 0; b = 0; c = 0;
}
Bellman(int aa, int bb, int cc) {
a = aa; b = bb; c = cc;//有参构造函数
}
}mapp[M];
int BellmanFord() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;//初始化距离
for (int i = 1; i <= k; i++) {
memcpy(backup,dis,sizeof(dis));//拷贝原数组 防止串联更新
for (int j = 1; j <= m; j++) {
Bellman now = mapp[j];
dis[now.b] = min(dis[now.b], backup[now.a] + now.c);//注意是原始数组的a值加上当前权值防止串联更新
}
}
if (dis[n] > 0x3f3f3f3f / 2)//可能存在负边 导致正无穷被更新 根据数据确定范围
return -1;
else return dis[n];
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int aa, bb, cc;
cin >> aa >> bb >> cc;
mapp[i] = Bellman(aa, bb, cc);
}
if (BellmanFord() == -1)
cout << "impossible" << endl;
else cout << BellmanFord() << endl;
return 0;
}
五、SPFA算法
由BellmanFord算法进行优化得来的
当BellmanFord算法 遍历所有边的时候 dis[b]=min[dis[b],dis[a]+c];
这个表达式只有dis[a]变小的时候才可能变小。
SPFA 既可以判断负环也可以判断无负环的
所以SPFA将dis[a]变小的点加入队列，并更新他们所连接的边，可以省去无用的迭代
核心操作
1.先将1点入队
2.将dis[a]变小的节点放入队列中
3.取出队头->t 把队头删掉 用t更新以t为起点的边
4.更新成功后把b加入队列，判断，如果队列中有b则不加入
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
int n, m, h[N], e[M], ne[M], wei[M], vis[N], dis[N], idx;
void add(int a, int b, int c) {
e[idx] = b;
wei[idx] = c; //有权重时，用邻接表存储图，在图中加入一条边
ne[idx] = h[a];
h[a] = idx++;
}
int SPFA() {
memset(dis, 0x3f, sizeof(dis));//初始化距离
dis[1] = 0;
queue<int> q; //定义队列 SPFA优化 队列中存储的是边权重减小的边 只有前驱减小了，他的后继才有可能减小
q.push(1);
vis[1] = 1;
while (q.size()) {
int now = q.front();
q.pop();
vis[now] = false;// 由于SPFA中存在负权边 所有可重复加入 此初与Dijkstra不同，由于Dijkstra 所有边权为正，所以最短路不会经过一个点两次
for (int i = h[now]; i != -1; i=ne[i]) {//核心操作，在边权重减小的边中，更新他的后继变小的边，
int j = e[i];
if (dis[j] > dis[now] + wei[i]) {
dis[j] = dis[now] + wei[i];
if (!vis[j]) {//如果这个点被更新了且不在队列中，则把他加入队列
q.push(j);
}
}
}
}
if (dis[n] == 0x3f3f3f3f)// 当队列为空时，SPFA算法已经帮我们找到了到n点的最短路径
return -1;
else return dis[n];
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (SPFA() == -1) {
cout << "impossible" << endl;
}
else cout << SPFA() << endl;
return 0;
}
六、 SPFA 判断负环
dis[x] : 表示当前 1~x的最短距离
cnt[x]: 表示当前最短路的边数
更新
dis[x]=dis[t]+w[i];
cnt[x]=cnt[t]+1; //从1~x的边数=从1~t的边数+1
如果cnt[x]>=n 意味着从1 到x 至少经过了n条边 ->至少经过了n+1个点->则存在环
因为每次更新路径都是在减少，所以环一定是负环
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = N * 2;
int n, m, h[N], e[M], ne[M], wei[M], vis[N], dis[N], cnt[N], idx;
//dis[N]代表到这个点的距离 cnt[N] 代表走到这个点经历了多少边
void add(int a, int b, int c) {
e[idx] = b;
wei[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool SPFA_Negative() {
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i);
vis[1] = 1; //从1号点可能走不到负环 所以从多个起点开始
}
while (q.size()) {
int now = q.front();
q.pop();
vis[now] = 0;
for (int i = h[now]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[now] + wei[i]) {
dis[j] = dis[now] + wei[i];
cnt[j] = cnt[now] + 1;//更新边的距离的时候把cnt也更新
if (cnt[j] >= n)
return true;//如果到某个点经历了大于n个点 则说明存在自环 因为距离都是往短了更新 所以存在负环
if (!vis[j]) {
q.push(j);
vis[j] = 1;
}
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (SPFA_Negative())
cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
六、多源最短路 Floyd算法(也可以处理负权，但不能有负环)
使用邻接矩阵存储
！！n为200经常使用Floyd
d[i,j] -> i到j的最短距离
d[k,i,j]->从 i点出发 只经过 1~k这些中间点到达j
原理 动态规划
核心操作
三重for 先循环k ，i和j的for顺序可以互换
for(k=1~n)
for(i=1~n)
for(j=1~n)
d[i,j]=min(d(i,j),d(i,k)+d(k,j
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f;
int dis[N][N];
int n, m, k;
void Floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) { //邻接矩阵存储图的初始化方式
for (int j = 1; j <= n; j++) {
if (i == j)
dis[i][j] = 0;
else dis[i][j] = INF;
}
}
while (m--) {
int a, b, c;
cin >> a >> b >> c;
dis[a][b] = min(dis[a][b], c);//存在重边和自环
}
Floyd();
while (k--) {
int i, j;
cin >> i >> j;
if (dis[i][j] > INF / 2)//由于存在负权边 所以判断不能到达时应判断INF/2
cout << "impossible" << endl;
else cout << dis[i][j] << endl;
}
return 0;
}
竟然是2年前的帖子了 请问有后续总结么哈哈
没了 亲
点赞
你是桂电科协的马丁吗
不是去不了那么好的学校，只是娶个id叫这个名字
哈哈
必须赞一个
谢谢~