///朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
///时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);//将每个点每个距离赋值为无穷大
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
cout<<t<<endl;
}
///堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
///时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int h[N],e[N],ne[N],idx,n,m,w[N];
int dist[N];
bool st[N];
typedef pair<int ,int>PII;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;/// 邻接表存储所有边
}
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;//创立小根堆
heap.push({0,1});/// first存储距离，second存储节点编号
while(!heap.empty())
{
auto t=heap.top();
heap.pop();
int ver=t.second,dis=t.first;
if(st[ver]) continue;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dis+w[i])
{
dist[j]=dis+w[i];
heap.push({dist[j],j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=dijkstra();
cout<<t<<endl;
}
///最短路计数,使用邻接表动态数组,bfs
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,mod=100003;
vector<int> g[N];
int dist[N];
bool vis[N];
int cnt[N];
int n,m;
void bfs()
{
memset(dist,0x3f3f3f,sizeof dist);
memset(vis,false,sizeof vis);
queue<int>que;
dist[1]=0;
cnt[1]=1;
que.push(1);
while(!que.empty())
{
int u=que.front();
que.pop();
if(vis[u]) continue;
vis[u]=true;
for(auto v:g[u])
{
if(!vis[v])
{
if(dist[v]>dist[u]+1)///如果此时不是1最短路,更新最短路
{
dist[v]=dist[u]+1;
cnt[v]=cnt[u];
cnt[v]%=mod;
que.push(v);
}
else if(dist[v]==dist[u]+1)///如果走的路是最短路,就在这个地方加上1;
{
cnt[v]+=cnt[u];
cnt[v]%=mod;
}
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);///储存邻接表
g[b].push_back(a);
}
bfs();
for(int i=1;i<=n;i++)
cout<<cnt[i]<<endl;
return 0;
}
///ballman-ford
///存在负边时使用
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,k;
int dist[N],backup[N];
struct node
{
int a,b,w;
}edge[N];
int ballman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++)
{
memcpy(backup,dist,sizeof dist);
for(int j=0;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]>0x3f3f/2) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
int t =ballman_ford();
if(t==-1) puts("impossible");
else cout<<t<<endl;
return 0;
}
///SPFA路径
///使用的邻接表储存
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int>que;
que.push(1);
st[1]=true;
while(!que.empty())
{
int now=que.front();
que.pop();
st[now]=false;
for(int i=h[now];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[now]+w[i])
{
dist[j]=dist[now]+w[i];
if(!st[j])
{
que.push(j);
st[j]=true;
}
}
}
}
if(dist[n]>0x3f3f/2) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=spfa();
if(t==-1) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}
///更加详细的spfa
#include <bits/stdc++.h>
using namespace std;
const int N = 2030, M = N * 50; //N为顶点数，M为边数
//数组构造邻接表, n为定点数，m为边数
int n, m
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
queue<int> q;
bool st[N];
// 添加一条边a->b，边权为c
void add(int a, int b, int c)
{
//e[idx]指的是编号为idx的边的去向为何处，h[a]存储的是从a出发的所有边的单链表表头
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa() // 求1号点到n号点的最短路距离
{
memset(dist, 0x3f, sizeof dist); //0x3f代表最大值，最小值可用0xcf
dist[1] = 0;
q.push(1);
st[1] = true;
while (q.size()) //while循环控制出队
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) //for循环控制入队+更新
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
// cnt[j] = cnt[t] + 1; // 用于判断是否存在负环
// pre[i] = t; // 用于记录前驱节点(记录路径)
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
// if(cnt[j] >= n) return true; // 用于判断是否存在负环
}
// 最短路计数要区分dist[j] > 和 == 的情况，不能只讨论dist[j] > dist[t] + w[i]
/**
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t]
}
else if (dist[j] == dist[t] + w[i]) {
cnt[i] += cnt[t]; //最短路计数
}
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
*/
}
}
}
int main(){
memset(h, -1, sizeof h);
... //需先通过add函数，采取邻接表的方式构造好图
spfa();
... //输出路径权值和、判断是否有负环、输出最短路径...等操作
/** 记录路径操作 */
stack<int> help; //遍历前驱节点，压入栈中，再取出来时可以变为正序的
for (int i = n; ~i; i=pre[i]) help.push(i); // n为路径终点
while (help.size()) {
printf("%d ", help.top());
help.pop();
}
}
///二维数组存SPFA
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node
{
int b,w;
}e;
int n,m;
int dist[N];
bool st[N];
vector<node>g[N];
int spfa()
{
memset(dist,0x3f3f,sizeof dist);
dist[1]=0;
queue<int>que;
que.push(1);
st[1]=true;///表示我们的这个点已经入队列了
while(!que.empty())
{
int now=que.front();
que.pop();
st[now]=false;///队头出去了,那就是这个点不在这个队列里了标记false;
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].b;
if(dist[v]>dist[now]+g[now][i].w)
{
dist[v]=dist[now]+g[now][i].w;
if(!st[v])///如果队列里面没有他,再加入队列;
{
st[v]=true;
que.push(v);
}
}
}
}
if(dist[n]>0x3f3f/2) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a;
cin>>a>>e.b>>e.w;
g[a].push_back(e);///存入数据
}
int t=spfa();
if(t==-1) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}
///SPFA判断负环
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node
{
int b,w;
}e;
int n,m;
int dist[N],cnt[N];
bool st[N];
vector<node>g[N];
bool spfa()
{
queue<int>que;
for(int i=1;i<=n;i++)///有可能从起点1,走不到负环的位置,所以1只需要把所有点都加入队列遍历即可
{
st[i]=true;
que.push(i);
}
while(!que.empty())
{
int now=que.front();
que.pop();
st[now]=false;///队头出去了,那就是这个点不在这个队列里了标记false;
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].b;
if(dist[v]>dist[now]+g[now][i].w)
{
dist[v]=dist[now]+g[now][i].w;
cnt[v]=cnt[now]+1;///这个代表的是当前这条路的边数
if(cnt[v]>=n) return true;///如果,我是说如果当前路的边数已经大于n了,那很明显存在负环;
if(!st[v])///如果队列里面没有他,再加入队列;
{
st[v]=true;
que.push(v);
}
}
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a;
cin>>a>>e.b>>e.w;
g[a].push_back(e);///存入数据
}
if(spfa()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
///floyd算法,适用于多个询问,复杂度0n3
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k;
int d[N][N];
void floyd()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int x=1;x<=n;x++)
d[j][x]=min(d[j][x],d[j][i]+d[i][x]);
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) d[i][j]=0;
else d[i][j]=1e9;
while(m--)
{
int a,b,w;
cin>>a>>b>>w;
d[a][b]=min(d[a][b],w);
}
floyd();
while(k--)
{
int a,b;
cin>>a>>b;
if(d[a][b]>1e9/2) cout<<"impossible"<<endl;
else cout<<d[a][b]<<endl;
}
return 0;
}
///分层图
//https://blog.csdn.net/qq_45735851/article/details/108219481?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168420864216800222869973%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168420864216800222869973&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-108219481-null-null.142^v87^control,239^v2^insert_chatgpt&utm_term=%E5%88%86%E5%B1%82%E5%9B%BE%E6%9C%80%E7%9F%AD%E8%B7%AF&spm=1018.2226.3001.4187
///分层图最经典的例题之一
///可以试想一下,咱们最短路是一个图,分层图的意思是创建多个图,然后每个图都不一样,遍历完之后找到最优解
///可以看出来分层图难在建图
#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
int n,m,s,k,t,idx;
int e[N],ne[N],h[N],dist[N],w[N];
bool vis[N];
typedef pair<int,int>pii;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()///标准模板
{
priority_queue<pii,vector<pii>,greater<pii>> que;
memset(dist,0x3f3f3f,sizeof dist);
dist[s]=0;
que.push({0,s});
while(!que.empty())
{
auto now=que.top();
que.pop();
int y=now.first,x=now.second;
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>y+w[i])
{
dist[j]=y+w[i];
que.push({dist[j],j});
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m>>k>>s>>t;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
//add(b,a,c);
for(int j=1;j<=k;j++)///建图
{
add(j*n+a,j*n+b,c);///把一层建好
//add(j*n+b,j*n+a,c);
add((j-1)*n+a,j*n+b,0);///把上一层建好,代表从上到下走0的距离;
// add((j-1)*n+b,j*n+a,0);
}
}
for(int i=0;i<k;i++) add(i*n+t,(i+1)*n+t,0);///有可能答案不需要非要用完k次免费次数,所以这里把所有终点都用距离为0连起来;
dijkstra();
int minn=0x3f;
for(int i=0;i<=k;i++) minn=min(minn,dist[i*n+t]);///遍历所有终点,有可能没必要用完k次;
cout<<minn;
return 0;
}
///floyd算法的应用
//https://www.luogu.com.cn/record/110497608
///floyd算法应用与求每个点到任意一点的最短距离,然后根据此算法就可以按照题目要求的路径算出最短路径来
///不需要建图,三重暴力循环解决战斗
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,num[100005],d[N][N],res;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>num[i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>d[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
int st=1,ed=n;
for(int i=1;i<=m;i++)
{
res+=d[st][num[i]];
st=num[i];
}
res+=d[st][ed];
cout<<res<<endl;
return 0;
}
///floyd 应用2 变形
//https://www.luogu.com.cn/problem/B3611
#include<bits/stdc++.h>
using namespace std;
const int N=500;
int n,d[N][N],mp[N][N];
int main()
{
cin>>n;;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>d[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
d[j][k]=max(d[j][k],min(d[j][i],d[i][k]));///1表示为连通,0表示为不连通,试想一下,如果d[j][k]和另一个有一个为1,那是不是就是可以连通?
///但是这里为什么第二个要取min呢,如果这两者有一个为0,说明,j和k之间没有中转站,此时如果j和k不是直接连的也就是,d[j][k]不是1,那么这两点不可能连上;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<d[i][j]<<" ";
cout<<endl;
}
return 0;
}
标签：图论,dist,idx,int,st,que,now From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17428001.html