做会员卡的网站在线制作/seo搜索引擎专员

SPFA算法模板题，以下给出AC代码，具体思路详见注释。
（SPFA运行效率低于Dijkstra，若出题人构造出毒瘤数据可以让SPFA超时，这题是弱化版，所以能过）

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=5e5+10;
int n,m,x,y,z,s,cnt,dis[N],vis[N],head[N];
struct edge
{int w,to,next;
}e[M];//定义边的三个信息，w表示边权，to表示边的终点，next表示上一条边
void add(int x,int y,int z)//链式前向星存边
{e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];//next表示以x为起点的上一条边的编号head[x]=cnt++;//head[x]表示以x为起点的最后一条边的编号
}
queue<int>q;
void spfa()
{q.push(s);//起点入队dis[s]=0;//起点到自身距离为0while(!q.empty()){int u=q.front();q.pop();vis[u]=0;//出队标记for(int i=head[u];i!=-1;i=e[i].next)//遍历以u为起点的所有边{int v=e[i].to;if(dis[u]+e[i].w<dis[v]){dis[v]=dis[u]+e[i].w;//更新最短距离if(vis[v]==0)q.push(v),vis[v]=1;//入队标记}}}
}
int main()
{ios::sync_with_stdio(false);cin>>n>>m>>s;memset(head,-1,sizeof(head));//head数组初始化for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);}for(int i=1;i<=n;i++)//dis数组初始化dis[i]=2147483647;spfa();for(int i=1;i<=n;i++)i==n?printf("%d\n",dis[i]):printf("%d ",dis[i]);return 0;
}

Dijkstra算法模板题，以下给出AC代码，具体思路详见注释。
（本题用SPFA会超时，只能用Dijkstra）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,m,x,y,z,s,cnt,dis[N],vis[N],head[N];
struct edge
{int w,to,next;
}e[M];//定义边的三个信息，w表示边权，to表示边的终点，next表示上一条边
void add(int x,int y,int z)//链式前向星存边
{e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];//next表示以x为起点的上一条边的编号head[x]=cnt++;//head[x]表示以x为起点的最后一条边的编号
}
struct node
{int u,w;//u为点的编号，w为到u点的最短路即dis[u]
};
bool operator < (const node &s1,const node &s2)//重载运算符，优先队列中的自定义排序
{return s1.w>s2.w;}//注意写大于号还是小于号与实际的符号相反，实际是小于号，则要写大于号
priority_queue<node>q;
void dijkstra()
{q.push({s,0});//起点入队dis[s]=0;//起点到自身距离为0while(!q.empty()){int u=q.top().u;q.pop();if(vis[u])continue;//保证每个点只被访问一次vis[u]=1;for(int i=head[u];i!=-1;i=e[i].next)//遍历以u为起点的所有边{int v=e[i].to;if(dis[u]+e[i].w<dis[v]){dis[v]=dis[u]+e[i].w;//更新最短距离q.push({v,dis[v]});}}}
}
int main()
{ios::sync_with_stdio(false);cin>>n>>m>>s;memset(head,-1,sizeof(head));//head数组初始化for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);}for(int i=1;i<=n;i++)//dis数组初始化dis[i]=2147483647;dijkstra();for(int i=1;i<=n;i++)i==n?printf("%d\n",dis[i]):printf("%d ",dis[i]);return 0;
}

讨论重载运算符的写法：https://www.luogu.org/blog/53164/dijkstra-heap

SPFA代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=100003;
int n,m,x,y,cnt,dis[N],ans[N],vis[N],head[M];
struct edge
{int w,to,next;
}e[M<<1];//无向图，边数乘2
void add(int x,int y,int z)
{e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt++;
}
queue<int>q;
void spfa()
{q.push(1);dis[1]=0;ans[1]=1;//从1开始，到1自身的最短路径只有1条，最短路径长度为0while(!q.empty()){int x=q.front();q.pop();vis[x]=0;//出队标记for(int i=head[x];i!=-1;i=e[i].next){int to=e[i].to;if(dis[to]>dis[x]+e[i].w){ans[to]=ans[x];dis[to]=dis[x]+e[i].w;if(!vis[to]){vis[to]=1;//入队标记q.push(to);}}else if(dis[to]==dis[x]+e[i].w)ans[to]=(ans[to]+ans[x])%mod;}}
}
int main()
{ios::sync_with_stdio(false);memset(head,-1,sizeof(head));memset(dis,0x3f,sizeof(dis));cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;add(x,y,1);add(y,x,1);//注意是无向图，输入的是一条边的信息，实际上要存储的是两条边的信息(还包括反向的)}spfa();for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}

Dijkstra代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10,mod=100003;
int n,m,x,y,cnt,dis[N],ans[N],vis[N],head[M];
struct edge
{int w,to,next;
}e[M<<1];//无向图，边数乘2
void add(int x,int y,int z)
{e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt++;
}
struct node
{int w,now;bool operator < (const node &x) const{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{q.push({0,1});dis[1]=0;ans[1]=1;//从1开始，到1自身的最短路径只有1条，最短路径长度为0while(!q.empty()){int x=q.top().now;q.pop();if(vis[x])continue;vis[x]=1;for(int i=head[x];i!=-1;i=e[i].next){int to=e[i].to;if(dis[to]>dis[x]+e[i].w){ans[to]=ans[x];dis[to]=dis[x]+e[i].w;q.push({dis[to],to});}else if(dis[to]==dis[x]+e[i].w)ans[to]=(ans[to]+ans[x])%mod;}}
}
int main()
{ios::sync_with_stdio(false);memset(head,-1,sizeof(head));memset(dis,0x3f,sizeof(dis));cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;add(x,y,1);add(y,x,1);//注意是无向图，输入的是一条边的信息，实际上要存储的是两条边的信息(还包括反向的)}dijkstra();for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,t,c,cnt,x[N],y[N],z[N],dis[N],vis[N],head[N];
struct edge
{int w,to,next;
}e[N];
void add(int x,int y,int z)
{e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt++;
}
struct node
{int w,now;bool operator < (const node &x) const{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{q.push({0,1});dis[1]=0;while(!q.empty()){int x=q.top().now;q.pop();if(vis[x])continue;vis[x]=1;for(int i=head[x];i!=-1;i=e[i].next){int to=e[i].to;if(dis[x]+e[i].w<dis[to]){dis[to]=dis[x]+e[i].w;q.push({dis[to],to});}}}
}
int main()
{ios::sync_with_stdio(false);cin>>t;char f;while(t--){memset(head,-1,sizeof(head));memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));cnt=0;cin>>n>>m;c=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>f;if(f=='/'){x[++c]=(i-1)*(m+1)+j+1,y[c]=x[c]+m,z[c]=0;x[++c]=(i-1)*(m+1)+j,y[c]=x[c]+m+2,z[c]=1;}else{x[++c]=(i-1)*(m+1)+j,y[c]=x[c]+m+2,z[c]=0;x[++c]=(i-1)*(m+1)+j+1,y[c]=x[c]+m,z[c]=1;}}for(int i=1;i<=c;i++){add(x[i],y[i],z[i]);add(y[i],x[i],z[i]);//注意是双向的无向图！！！}dijkstra();if(dis[(n+1)*(m+1)]==0x3f3f3f3f)printf("NO SOLUTION\n");else printf("%d\n",dis[(n+1)*(m+1)]);}return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e6+10;
int n,m,f,x,y,z,cnt,ans,dis[N],vis[N],head[M],flag[N][N],pre[N];
struct edge
{int w,to,next;
}e[M];
void add(int x,int y,int z)
{e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt++;
}
struct node
{int w,now;bool operator < (const node &x) const{return w>x.w;}
};
priority_queue<node>q;
void dijkstra()
{memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));q.push({0,1});dis[1]=0;while(!q.empty()){int x=q.top().now;q.pop();if(vis[x])continue;vis[x]=1;for(int i=head[x];i!=-1;i=e[i].next){int to=e[i].to;if(flag[x][to]==0&&dis[to]>dis[x]+e[i].w){if(f==0)pre[to]=x;dis[to]=dis[x]+e[i].w;q.push({dis[to],to});}}}
}
int main()
{ios::sync_with_stdio(false);memset(head,-1,sizeof(head));cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}dijkstra();f=1;for(int i=n;i!=1;i=pre[i]){flag[pre[i]][i]=1;flag[i][pre[i]]=1;dijkstra();flag[pre[i]][i]=0;flag[i][pre[i]]=0;ans=max(ans,dis[n]);}printf("%d\n",ans);return 0;
}

参考文章，最短路最长路整理：https://blog.csdn.net/yusiningxin/article/details/50758946