Week 9 图论
P5318 【深基18.例3】查找文献
-
思路：用vector存单向图，排序，深搜光搜
-
注意：“如果有很多篇文章可以参阅，请先看编号较小的那篇”，需要排序（按终点由小到大排列，终点相同则起点有小到大
#include<bits/stdc++.h> using namespace std; struct edge{ int u,v; }; vector <int> e[100001]; vector <edge> s; bool vis1[100001]={0},vis2[100001]={0}; bool cmp(edge x,edge y) { if(x.v==y.v) return x.u<y.u; else return x.v<y.v; } void dfs(int x)//深搜 { vis1[x]=1; cout<<x<<" "; for(int i=0;i<e[x].size();i++){ int point=s[e[x][i]].v; if(!vis1[point]){ dfs(point); } } } void bfs(int x) //广搜 { queue <int> q; q.push(x); cout<<x<<" "; vis2[x]=1; while(!q.empty()){ int fro=q.front(); for(int i=0;i<e[fro].size();i++){ int point=s[e[fro][i]].v; if(!vis2[point]){ q.push(point); cout<<point<<" "; vis2[point]=1; } } q.pop(); } } int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int x,y; cin>>x>>y; s.push_back((edge){x,y}); } sort(s.begin(),s.end(),cmp); for(int i=0;i<m;i++) e[s[i].u].push_back(i); dfs(1); cout<<endl; bfs(1); }
U80592 【模板】floyd
- 模板题直接套floyd就行
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const long long t=998244354;
int n,m;
long long f[505][505];
int main()
{
long long u,v,w;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=INF;
f[i][i]=0;
}
}
for(int i=0;i<m;i++)
{
cin>>u>>v>>w;
f[u][v]=min(w,f[u][v]);
f[v][u]=min(w,f[v][u]);
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
}
}
}
long long ans;
for(int i=1;i<=n;i++)
{
ans=0;
for(int j=1;j<=n;j++)
{
if(f[i][j]!=INF)
{ans=(ans+f[i][j])%t;}
}
cout<<ans<<endl;
}
}
P4779 【模板】单源最短路径（标准版）
- 模板题，dijkstra算法
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int to,w;
edge(int a,int b){
to=a;
w=b;
}
};
struct node
{
int id,s;
node(int a,int b){
id=a;
s=b;
}
bool operator >(const node c) const{
return s>c.s;
}
};
int n,m,be;
vector <edge> e[100005];
int dis[100005];
bool vis[100005];
void dijkstra(int be)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[be]=0;
priority_queue <node,vector<node>, greater<node> > Q;
Q.push(node(be,0));
while(!Q.empty())
{
node nd=Q.top();
Q.pop();
if(vis[nd.id])
continue;
vis[nd.id]=true;
for(int i=0;i<e[nd.id].size();++i)
{
edge y=e[nd.id][i];
if(vis[y.to])
continue;
if(dis[y.to]>y.w+nd.s)
{
dis[y.to]=y.w+nd.s;
Q.push(node(y.to,dis[y.to]));
}
}
}
}
int main()
{
cin>>n>>m>>be;
for(int i=1;i<=m;++i)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[a].push_back(edge(b,c));
}
dijkstra(be);
for(int i=1;i<=n;++i)
{
printf("%d ",dis[i]);
}
return 0;
}