一、单源最短路算法
最短路算法_yan__kai_的博客-CSDN博客
二、例题
1.acwing1129
题意解读：走过一条路存在花费c，求最小费用即求最短路。无向图
直接背模板：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;typedef pair<int,int> PII;
const int N =3000,M= 6200 * 2 + 10;int h[N],e[M],ne[M],w[M],idx;
int n,m;
int start,ed;
bool st[N];
int dist[N];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);priority_queue<PII,vector<PII>,greater<PII> > heap;dist[start]=0; heap.push({0,start});while(heap.size()){auto t=heap.top();heap.pop();int ver=t.second;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[ver]+w[i]){dist[j]=dist[ver]+w[i];heap.push({dist[j],j});}}}return dist[ed];}int main()
{cin>>n>>m>>start>>ed;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);add(a,b,w);add(b,a,w);}int t=dijkstra();printf("%d",t);
}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4279854/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。2.acwing1128
题意：从起点到其他各点的送信时间实际上仍然是最短路算法，，答案要求我们输出最短时间，实际上就是起点到其它各点的最长时间（最远的点收到通信即代表送信完成）
直接背板子，本着复习的态度，这里不再用dijkstra，而是用floyd算法
复习：floyd算法需要初始化自己到自己的距离为0，初始化其它距离为无穷
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N =110,INF=0x3f3f3f3f;int n,m;
int d[N][N];int main()
{cin>>n>>m;memset(d,0x3f,sizeof d);for(int i=1;i<=n;i++) d[i][i]=0;for(int i=0;i<m;i++){int a,b,w;cin>>a>>b>>w;d[a][b]=d[b][a]=min(d[a][b],w);}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}int res=0;for(int i=1;i<=n;i++)if(d[1][i]>=INF){res=-1;break;}else res=max(res,d[1][i]);cout<<res;return 0;
}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4279898/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。3.acwing1127
点数800，边数1500。求一次最短路mlogn，枚举所有点放黄油，复杂度mnlogn，本题数据量很小可以接受直接暴力枚举放黄油的点。
直接模板求最短路，然后算距离即可。本着复习的原则，本题用spfa算法
spfa算法认为，只有被更新过的点,才能更新后继的结点。即如果一个节点没有被更新过，那么再拿这个节点去更新其他结点是没有效果的。所以使用队列，存储被更新的结点，st表示这个节点是否在队列当中，防止队列里面加了相同的节点。
注意：st数组的使用、判断无解的条件。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;const int N =810,M=3000,INF=0x3f3f3f3f;int n,p,m;
int dist[N];
bool st[N];
int h[N],e[M],ne[M],w[M],idx;
int id[N];void add(int a,int b,int c)
{e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}int spfa(int start)
{memset(dist,0x3f,sizeof dist);memset(st,false,sizeof false);dist[start]=0;queue<int> q;q.push(start);st[start]=true;while(q.size()){int t=q.front();q.pop();st[t]=false;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];st[j]=true;q.push(j);}}}int res=0;for(int i=0;i<n;i++){int j=id[i];if(dist[j]==INF) return INF;res+=dist[j];}return res;
}int main()
{cin>>n>>p>>m;memset(h,-1,sizeof h);for(int i=0;i<n;i++) cin>>id[i];for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}int res=INF;for(int i=1;i<=p;i++) res=min(res,spfa(i));cout<<res;}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4279946/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。4.acwing1126
建图：人 作为点，A为起点B为终点，边长是扣除手续费，dist为保留原费用的百分比，即初始化A的dist为1，走向下一个点（假设扣除z%的手续费，即dist（a）*g，，g=（100-c）/100）
那么走到最后答案就是100/dist（b）
目标是让dist（b）尽量大，则跑最长路即可
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;const int N =2010;int n,m,S,T;
double g[N][N];
double dist[N];
bool st[N];void dijkstra()
{dist[S]=1;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++)if(!st[j]&&(t==-1||dist[t]<dist[j]))t=j;st[t]=true;for(int j=1;j<=n;j++)dist[j]=max(dist[j],dist[t]*g[t][j]);}}int main()
{cin>>n>>m;while(m--){int a,b,c;cin>>a>>b>>c;double z=(100.0-c)/100;g[a][b]=g[b][a]=max(g[a][b],z);}cin>>S>>T;dijkstra();printf("%.8lf",100/dist[T]);
}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4280167/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。5.acwing920
答案要求输出最少换乘次数。问题根本在如何建图使得求解方便上。
假设我们乘上了j号站，则我们下一步可选择到包含j号站的所有线路，的在j号站之后的所有站下车换乘。
据此考虑，我们把j号点与这条线路上之后的所有点加一条边，长度为1。这样就能使得建出来的图能够使用最短路算法求解。
因为长度为1，因此我们使用bfs算法即可求解最短路。
直接bfs求解的实际上是“坐车的次数”，答案应该是不换乘——0 和坐车的次数-1.
注意坐车的次数可以是0，因此答案表达式为
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
using namespace std;const int N =510;int m,n;
int dist[N];
bool g[N][N];
bool st[N];
int stop[N];void bfs()
{queue<int> q;memset(dist,0x3f,sizeof dist);q.push(1);dist[1]=0;while(q.size()){int t=q.front();q.pop();for(int i=1;i<=n;i++)if(g[t][i]&&dist[i]>dist[t]+1){dist[i]=dist[t]+1;q.push(i);}}
}int main()
{cin>>m>>n;string line;getline(cin,line);while(m--){getline(cin,line);stringstream ssin(line);int cnt=0,p;while(ssin>>p) stop[cnt++]=p;for(int j=0;j<cnt;j++)//每个站点 与之后的 所有站点建一条单向边for(int k=j+1;k<cnt;k++)g[stop[j]][stop[k]]=true;} bfs();//01bfs求最短路if(dist[n]==0x3f3f3f3f) puts("NO");else cout<<max(dist[n]-1,0);return 0;}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4327369/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。6.acwing903
题意：N=100，可以用邻接矩阵建图；物品--点，边--某个物品可以的替代品。边的意义即为，从这个替代品出发,花费代价w可以到达该物品，这样就可以用最短路。
与地位低的交易了，地位高度的不会和他交易：只能选择一个起点出发。
求解方法：我们总要选择一个起点出发，如何选择交给算法解决最好。因此我们可以设立一个虚拟原点，将它和所有物品连线，边的代价就是交易的代价。这样我们直接从虚拟源点开始跑最短路即可求得答案dist(1)。
等级差距超过了M则不能“间接交易”：因此我们需要限制间接交易的区间，区间必须要包括level1，并且为了防止遗漏最短路，必须要枚举所有包括了level1的区间。跑dijkstra受到等级区间限制，需要传入两个参数：等级最低限制和最高限制。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N =110 ,INF=0x3f3f3f3f;int level[N];
int w[N][N];
bool st[N];
int dist[N];
int m,n;int dijkstra(int down,int up)
{memset(dist,0x3f,sizeof dist);memset(st,false,sizeof st);dist[0]=0;for(int i=1;i<=n+1;i++)//n+1个点{int t=-1;for(int j=0;j<=n;j++)//注意是从0号点开始循环if((t==-1||dist[t]>dist[j])&&!st[j])t=j;st[t]=true;for(int j=1;j<=n;j++)if(level[j]>=down&&level[j]<=up)dist[j]=min(dist[j],dist[t]+w[t][j]);}return dist[1];
}int main()
{cin>>m>>n;memset(w,0x3f,sizeof w);for(int i=0;i<=n;i++) w[i][i]=0;for(int i=1;i<=n;i++){int price,cnt;cin>>price>>level[i]>>cnt;w[0][i]=min(price,w[0][i]);//虚拟原点 代表直接购买这件物品while(cnt--){int id,cost;cin>>id>>cost;w[id][i]=min(cost,w[id][i]);}}int res=INF;for(int i=level[1]-m;i<=level[1];i++) res=min(res,dijkstra(i,i+m));cout<<res;return 0;
}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4327877/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
