T1.P4779 【模板】单源最短路径（标准版）
思路：
1.这道题利用里vector建立邻接表。
2.运用优先队列重载运算符。
3.用的dijkstra算法的思想。
4.运用vis数组进行标记。
5.运用队列进行回溯。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int INF=1e9+5;
int dis[maxn];
bool vis[maxn];
int n,m,w;
struct node1
{
int v;
int s;
};
struct node2
{
int to;
int len;
};
bool operator<(node1 x,node1 y)
{
return x.s>y.s;
}
vector<node2> mp[maxn];
priority_queue<node1> s;
void dijkstra()
{
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[w]=0;
node1 p;
p.v=w,p.s=0;
s.push(p);
while(!s.empty())
{
int top=s.top().v;
s.pop();
if(vis[top]) continue;
for(int i=0;i<mp[top].size();i++)
{
int dv=mp[top][i].to;
int ds=mp[top][i].len;
if(dis[dv]>dis[top]+ds)
dis[dv]=dis[top]+ds;
node1 temp;
temp.s=dis[dv],temp.v=dv;
s.push(temp);
}
vis[top]=1;
}
}
int main()
{
int x,y,z;
cin>>n>>m>>w;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
node2 p;
p.to=y;p.len=z;
mp[x].push_back(p);
}
dijkstra();
for(int i=1;i<=n;i++)
cout<<dis[i]<<' ';
}T2. P5318 【深基18.例3】查找文献
思路：
由于输出的时候是按序号大小的先后进行输出，因此考虑用vector存图，进行排序。
其实就是建图然后排序然后分别进行dfs和bfs
注意并不是所有的文章都能被小K看完，我们只需要从1开始看，看完从1开始的强连通部分即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct edge
{
int u;
int v;
};
vector <int> mp[N];//存具体信息的二维vector --这样写有点别扭哇
vector <edge> edg;//存边的结构体 --
bool vis_dfs[N],vis_bfs[N];
bool cmp(edge x, edge y)
{
if(x.v==y.v) return x.u<y.u;//v相同按u排
else return x.v<y.v;//否则按v从大到小排序
}
void dfs(int x)
{
vis_dfs[x]=true;
cout<<x<<' ';
for(int i=0;i<mp[x].size();i++)
{
int next_point=edg[mp[x][i]].v;
if(!vis_dfs[next_point]) dfs(next_point);
}
}
void bfs(int x)
{
queue<int> q ;
q.push(x);
cout<<x<<' ';
vis_bfs[x]=true;
while(!q.empty())
{
int top=q.front();
for(int i=0;i<mp[top].size();i++)
{
int point=edg[mp[top][i]].v;
if(!vis_bfs[point])
{
q.push(point);
cout<<point<<' ';
vis_bfs[point]=true;
}
}
q.pop();
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
edg.push_back((edge){u,v});//初始化存边的s数组
}
sort(edg.begin(),edg.end(),cmp);
for(int i=0;i<m;i++) mp[edg[i].u].push_back(i);//初始化mp
dfs(1); //在mp[edg[i].u]（也就是i号边的起点edg[i].u连接的边的数组）中存入i号边
cout<<endl;
bfs(1);
}
T3.U80592 【模板】floyd
思路：
floyd的应用，主要是核心三行代码
通过三重循环(i,j,k)来求i与j的最短路，用i作为转折点
for(int i=1;i<=n;i++)//floyd精髓-*从j号顶点到k号顶点只经过前i号点的最短路程*
for(int j=1;j<=n;j++)//
for(int k=1;k<=n;k++)//
if(dis[j][i]+dis[i][k]<dis[j][k])//
dis[j][k]=dis[j][i]+dis[i][k];//
代码如下：
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244354;
long long dis[5005][5005];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dis[i][j]=INT_MAX;
dis[i][i]=0;
}
}
for(int i=1;i<=m;i++)
{
long long x,y,l;
cin>>x>>y>>l;
dis[x][y]=min(l,dis[x][y]);
dis[y][x]=min(l,dis[y][x]);
}
for(int i=1;i<=n;i++)//floyd精髓-*从j号顶点到k号顶点只经过前i号点的最短路程*
for(int j=1;j<=n;j++)//
for(int k=1;k<=n;k++)//
if(dis[j][i]+dis[i][k]<dis[j][k])//
dis[j][k]=dis[j][i]+dis[i][k];//
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=1;j<=n;j++)
if(dis[i][j]!=INT_MAX) ans=(ans+dis[i][j])%mod;
cout<<ans<<endl;
}
}p.s这周倒了😷..所以学的不是很深，dijkstra和他的堆优化还是云里雾里的感觉(⊙_⊙)
下周努努力把这玩意儿弄明白！！文章来源：https://www.toymoban.com/news/detail-597968.html
文章来源地址https://www.toymoban.com/news/detail-597968.html
到了这里，关于NEUQ-ACM week9的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
