最短路问题+最小生成树
1.Floyd算法
能解决大多数的图 但是复杂度大，时间复杂度O（N^3)
对于Floyd而已一次预处理后可以知道任意两点的最短距离，值得注意的是要先将dist初始化，i==j情况下为0，即自己和自己的距离，千万不要inf，然后就是三次for遍历跑一次
初始化：
int k;cin >> n >> m >> k;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)dist[i][j] = i == j ? 0 : inf;核心算法：
void Floyd() {for (int k = 1; k <= n; ++ k){for (int j = 1; j <= n; ++j){for (int g = 1; g <= n; ++g){dist[j][g] = min(dist[j][g], dist[j][k] + dist[k][g]);}}}
}2.算法
可以解决负环问题
-floyd算法基础模板题牛客
代码实现
#include
#include
#include
#include
#include
#include
#include 当然也可以这个样子存图，效果一样：
int n, m, s, t;
int dis[20000];struct node
{int u, v, w;
};
vectorarr;void Bellman_Ford(int s) {for (int i = 1; i <= n; ++i) {dis[i] = inf;}dis[s] = 0;for (int i = 1; i < n; ++i){for (int j = 0; j < 2 * m; ++j){int u = arr[j].u, v = arr[j].v, w = arr[j].w;if (dis[v] >dis[u] + w )dis[v] = dis[u] + w;}}}void Solve() {cin >> n >> m >> s >> t;for (int i = 0; i < m; ++i){int u, v, w;cin >> u >> v >> w;arr.push_back({ u,v,w });arr.push_back({ v,u,w });}Bellman_Ford(s);if (dis[t] > inf / 2)cout << -1 << endl;else cout << dis[t] << endl;} 对于 算法的队列优化 SPFA优化;
//关于为什么要更新n-1次的问题！！！！
for k:n-1 这里的k是不超过k条边 如果k==n，一定存在负环！！！！！！
SPFA优化代码: 它也可以判断是否存在负环！！！！
int n, m, s, t;
int dis[20000];
bool vis[20000];
struct node
{int v, w;
};
vectorarr[20000];
int cnt[20000];void SPFA(int s) {for (int i = 0; i <= n; ++i)dis[i] = inf;dis[s] = 0; vis[s] = true;queueq;q.push(s);while (!q.empty()){int t = q.front();q.pop();vis[t] = false;//使得队首可以入队for (int i = 0; i < arr[t].size(); ++i) {int j = arr[t][i].v;int w = arr[t][i].w;if (dis[j] > dis[t] + w) {dis[j] = dis[t] + w;cnt[j] = cnt[t] + 1;//判断负环//if (cnt[j] >= n) 等于n说明了负环！！！//{// cout << "找到了负环" << endl;//}if (!vis[j])q.push(j), vis[j] = true;}}}
}
:
是不是存在负环是要把所有点压入queue，因为题目不是求从1点开始的负环，是所有点的负环！！！如果改成从1开始的负环就不需要！！！
for (int i = 1; i <= n; ++i)q.push(i);558291c1d53f1fdfae825db26169cc9c
3.1.求最短路 I：
朴素的()算法：
void Dij(int s)
{for (int i = 0; i <= n; ++i)dis[i] = inf, vis[i] = false;dis[s] = 0;for (int i = 1; i <= n; ++i) {//循环n次int t = -1;for (int j = 1; j <=n; ++j) {//找未标记中最小的dis的节点xif (!vis[i] && (t == -1 || dis[j] < dis[t]))t = j;if (t == -1)return;vis[t] = true;for (int j = 1; j <=n; ++j)//从想出发更新dis[j] = min(dis[j], dis[t] + arr[t][j]);}}
}优先队列堆优化的算法：
void Dijkstra(int s) {for (int i = 0; i <= n; ++i)dis[i] = inf, vis[i] = false;dis[s] = 0;priority_queue, greater >q;q.push({ 0,s });//0是dis， s是当然点while(!q.empty()){int t = q.top().second;//取出队首q.pop();if (vis[t])continue;//访问了就continuevis[t] = true;for (int i = 0, len = arr[t].size(); i < len; ++i) {//对于t这个点遍历更新和它匹配的点int v = arr[t][i].v, w = arr[t][i].w;if (dis[v] > dis[t] + w)//符合就更新后压入dis[v] = dis[t] + w, q.push({ dis[v],v });}}
} void Dijkstra(int s) {for(int i=0; i<=2*n; ++i)dis[i]=inf,vis[i]= false;dis[s]=0;priority_queue,greater >q;//first is dis y is startwhile (!q.empty()) { //清空队列q.pop();}q.push({0,s});while(!q.empty()) {int t=q.top().second;q.pop();if(vis[t])continue;vis[t]=true;for(int i=0,len=arr[t].size(); idis[t]+w)dis[v]=dis[t]+w,q.push({dis[v],v});}}
} !!!!!题源this->
这是狄斯克算法，权值有向图；数据域小直接开数组：当然这是没有优化的算法，复杂度为O(n^2)，我们可以采取优先队列进行最短路堆优化
#include
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
typedef long long ll;
int a[505][505],dis[5000];//dis为到达节点的路，a为图
bool vis[5000];//标记集合
void Solve() {int n,m;cin>>n>>m;memset(a,inf,sizeof a);//inf 数组afor(int i=1;i<=m;++i){int x,y,w;cin>>x>>y>>w;a[x][y]=min(a[x][y],w);}// 存图for(int i=1;i<=n;++i)a[i][i]=0;memset(dis,inf,sizeof dis);//dis INFdis[1]=0;for(int cnt=1;cnt<=n;++cnt)//扩扑n次{int min_val=inf,x;for(int i=1;i<=n;++i)//更新最短路if(!vis[i]&&dis[i]< min_val)min_val=dis[i],x=i;vis[x]=true;//标记已经用过for(int y=1;y<=n;++y)//更新dis[y]=min(dis[y],dis[x]+a[x][y]);}if(dis[n]==inf)cout<<-1< 3.2.求最短路 II（最短路堆优化）： 题源在这里哦
显然本题 数据域范围过大存图要么连接表要么开维克多数组，这里我们使用优先队列，这个样子可以对最短路堆优化 连接表：
//连接表
const int MAX_N=2e5+5,MAX_M=2e5+5;
int head[MAX_N],ver[MAX_M],edge[MAX_M],nxt[MAX_M],tot;
//插入一条x到y长度z的有向边
void add(int x,int y,int z)
{tot++;ver[tot]=y;edge[tot]=z;nxt[tot]=head[x];//在head[x]这条链开头插入新点head[x]=tot;
}
AC代码：注意的是优先队列是大顶堆，降序，可以加-使其升序或者重载
#include
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define inf_max 0x7f7f7f7f
typedef long long ll;const int MAX_N=2e5+5,MAX_M=2e5+5;
int head[MAX_N],ver[MAX_M],edge[MAX_M],nxt[MAX_M],tot;
//插入一条x到y长度z的有向边
void add(int x,int y,int z)
{tot++;ver[tot]=y;edge[tot]=z;nxt[tot]=head[x];//在head[x]这条链开头插入新点head[x]=tot;
}
int n,m,dis[MAX_M];
bool vis[MAX_M];
//pair(dist[x],x)
struct com{bool operator()(paira,pairb){return a.first > q;//大顶堆;
void Solve() {cin>>n>>m;for(int i=1;i<=m;++i){int x,y,z;cin>>x>>y>>z;add(x,y,z);}//存图memset(dis,inf_max,sizeof dis);dis[1]=0;q.push(make_pair(0,1));while(!q.empty()){int x=q.top().second;q.pop();if(vis[x])continue;vis[x]=true;for(int i=head[x];i;i=nxt[i]){int y=ver[i],z=edge[i];if(dis[y]>dis[x]+z){dis[y]=dis[x]+z;q.push(make_pair(-dis[y],y));}}}if(dis[n]==inf_max)cout<<-1< 4.路径打印和路径统计问题
路径统计问题-洛谷
最短路典型问题： 1.有边数限制的最短路
有边数限制的最短路--
题解：
值得一提的是这题只可以算法，因为外层k循环是使得不超过k层边！！！
//防止串联，添加备份！！！！！
back干啥使的
back[j]表示每次进入第2重循环的dist数组的备份。
如果不加这个备份的话有可能会发生节点最短距离的串连；
比如说：
图1
现在从3号结点走到4号节点要想进行松弛操作就必须先得到dist[3]，要想得到dist[3]就得知道dist[2]；
dist[2]=2，现在dist[3]是正无穷，用2号结点来更新3号结点，dist[3]=2+3=5;
现在要更新dist[4]了，此时dist[4]=正无穷
出现问题了，dist[4]是用dist[3]是用正无穷来更新还是5呢
用dist[3]=5来更新那是下一次i迭代的事情；
这道题说是不经过k条边，说不定下一次就到k条边了，所以还是得用正无穷来更新的
#include
#include
using namespace std;
#define Fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef pair PII;
#define SQR(i) fixed<arr[10500];
int dis[10500];int back[N];//备份数组放置串联
void Bellman_Ford(int s) {memset(dis,inf,sizeof dis);dis[1] = 0;for(int k=0;k dis[u] + w)dis[v] = dis[u] + w;dis[v]=min(dis[v],back[u]+w);}}}
}void Solve() {cin>>n>>m>>s;for(int i=0; i>u>>v>>w;arr[u].push_back({v,w});// arr[v].push_back({u,w});}Bellman_Ford(s);if(dis[n]>inf/2)cout<<"impossible"< 当然本题也可以不需要邻接表！！
#include
using namespace std;
const int N=100010;
int dist[N],backup[N];
int k,n,m;
struct edge{int a;int b;int w;
}edge[N];
int bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=1;i<=k;i++){memcpy(backup,dist,sizeof dist);for(int j=1;j<=m;j++){int a=edge[j].a,b=edge[j].b,w=edge[j].w;dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>=0x3f3f3f3f/2)return -1;else return dist[n];
}
int main()
{cin>>n>>m>>k;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;edge[i].a=a,edge[i].b=b,edge[i].w=c;}int t=bellman_ford();if(t==-1)puts("impossible");else cout< 5.最小生成树 1、什么是树
如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。
参考文章！最小生成树 2..prim（）算法
int prime()
{//1memset(d,0x3f,sizeof d);d[1] = 0;//2int res = 0;//权重之和for(int i = 0;i d[j]))//t = j;}if(d[t] == INF) return INF;//(3)-把点t加到集合当中去，更新权值res += d[t];st[t] = true;//(2)for(int j = 1;j<=n;j++) d[j] = min(d[j],g[t][j]);}return res;
}
3.算法
先将边权重按照从小到大排序，然后依次遍历对于不在同一集合的进行合并，ans是答案，使用了并查集知识，cnt
算法题目
int n, m;
int ans;//最小权重和
int p[N];
struct edge {int a, b, w;//重载> n >> m;for (int i = 0; i < m; ++i){int u, v, w;cin >> edge[i].a >> edge[i].b >> edge[i].w;}int t = Kruskal();if (t < n - 1)cout << "impossible" << endl;else cout << ans << endl;
} 
