标签：总结 8.5 int back vis maxn push dist 四周
1dijkstra堆优化练习
1）邮寄员寄信
题目
多次运用最短路
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e3+10;
struct node{
int u,w;
//顺序好像不能错
};
bool vis[maxn];
int dist[maxn];
vector<node> g[maxn];
void dijk(int s)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
//注意q是咋写的
dist[s]=0;
q.push({0,s});
while(q.size()!=0)
{
int u=q.top().second;
//只取了点，没有q.top.first=w，自己写的逻辑有点问题
//注意是top后有括号
//优先队列默认按第一个排序，所以pair的first要放权值
q.pop();
//用过了这个点松弛所以我们要弹出
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<g[u].size(); i++)
{
//i起始是0
//用u更新距离
int d=g[u][i].w;
int v=g[u][i].u;
if(dist[v]>dist[u]+d)
{
dist[v]=dist[u]+d;
q.push({dist[v],v});
//把和u有关的点放进去
}
}
}
}
int main()
{ memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
long long sum=0;
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
// g[a].u=b;
// g[a].w=c;
//这么写会报错
g[a].push_back({b,c});
}
dijk(1);
for(int i=1;i<=n;i++)
sum+=dist[i];
for(int i=2;i<=n;i++)
{
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
dijk(i);
sum+=dist[1];
}
cout<<sum<<endl;
}
2）最短路（无权值）
代码（以前）
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
#define pii pair<int, int>
const int N = 1e5 + 10;
vector<int> v[N];
int d[N];
void solve()
{
int n, m, k, Q;
cin >> n >> m >> k >> Q;
queue<int> q;
for (int i = 1; i <= k; i++)
{
int x;
cin >> x;
d[x] = 1;
q.push(x);
}
while (m--)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
while (q.size())
{
auto t = q.front();
q.pop();
for (auto j : v[t])
{
if (!d[j])
{
q.push(j);
d[j] = d[t] + 1;
}
}
}
while (Q--)
{
int ed;
cin >> ed;
cout << d[ed] - 1 << '\n';
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(20);
int t = 1;
while (t--)
solve();
}
遍历起点终点会超时re
#include<bits/stdc++.h>
using namespace std;
int n,m,k,q;
const int maxn=1e4+10;
struct node{
int u,w;
};
bool vis[maxn];
int dist[maxn];
vector<node> g[maxn];
int qd[maxn];
int zd[maxn];
void dijk(int s)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
dist[s]=0;
q.push({0,s});
while(q.size()!=0)
{
int u=q.top().second;
//只取了点，没有q.top.first=w，自己写的逻辑有点问题
//注意是top后有括号
//优先队列默认按第一个排序，所以pair的first要放权值
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<g[u].size(); i++)
{
//i起始是0
//用u更新距离
int d=g[u][i].w;
int v=g[u][i].u;
if(dist[v]>dist[u]+d)
{
dist[v]=dist[u]+d;
q.push({dist[v],v});
//记得把他放回去
}
}
}
}
int main()
{ memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
long long sum=0;
cin>>n>>m>>k>>q;
for(int i=0;i<k;i++)
cin>>qd[i];
while(m--)
{
int a,b;
cin>>a>>b;
// g[a].u=b;
// g[a].w=c;
//这么写会报错
g[a].push_back({b,1});
g[b].push_back({a,1});
//无向图！！
}
// for(int i=0;i<maxn;i++)g[i].push_back({i,0});
for(int i=0;i<q;i++)
cin>>zd[i];
for(int i=0;i<q;i++)
{
int minn=1e9+10;
for(int j=0;j<k;j++)
{
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
dijk(qd[j]);
// minn=min(minn,dist[i]);
minn = min(minn, dist[zd[i]]);
//i不是终点，zd[i]才是。这样还是会re
}
cout<<minn<<endl;
}
}
调完
#include<bits/stdc++.h>
using namespace std;
int n,m,k,q;
const int maxn=1e6+10;
int s[maxn];
struct node
{
int u,w;
};
bool vis[maxn];
int dist[maxn];
vector<node> g[maxn];
void dijk(int s)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
for (int i = 0; i <= n; i++)dist[i] = (int)1e18;
dist[s]=0;
q.push({0,s});
while(q.size()!=0)
{
int u=q.top().second;
//只取了点，没有q.top.first=w，自己写的逻辑有点问题
//注意是top后有括号
//优先队列默认按第一个排序，所以pair的first要放权值
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=0; i<g[u].size(); i++)
{
//i起始是0
//用u更新距离
int d=g[u][i].w;
int v=g[u][i].u;
if(dist[v]>dist[u]+d)
{
dist[v]=dist[u]+d;
q.push({dist[v],v});
//记得把他放回去
}
}
}
}
int main()
{
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
cin>>n>>m>>k>>q;
for (int i = 1; i <= k; i++)cin >> s[i];
while(m--)
{
int a,b;
cin>>a>>b;
// g[a].u=b;
// g[a].w=c;
//这么写会报错
g[a].push_back({b,1});
g[b].push_back({a,1});
}
// for (int i = 1; i <= m; i++)
// {
// int a, b;
// cin >> a >> b;
// g[a].push_back({ b,1 });
// g[b].push_back({ a,1 });
// }
for (int i = 1; i <= k; i++)
g[0].push_back({ s[i],0 });
dijk(0);
while (q--)
{
int x;
cin >> x;
if (dist[x] != (int)1e18)cout << dist[x] << endl;
else cout << -1 << endl;
}
}
2 讲课（栈和队列）
课件
标签：总结,
8.5,
int,
back,
vis,
maxn,
push,
dist,
四周
From： https://www.cnblogs.com/hoshino-/p/18342845