首页 > 其他分享 >Living-Dream 系列笔记 第41期

Living-Dream 系列笔记 第41期

时间:2024-03-02 16:56:57浏览次数:25  
标签:Living pq int 41 vis dijkstra now Dream dis

稍微讲一下 dijkstra qwq。

dijkstra、bellman-ford(or spfa)、bfs 的区别:

  • dijkstra 以为研究对象;

  • bellman-ford / spfa 则以为研究对象;

  • 而 bfs 可以看作边权为 \(1\)(or 全都相同)的 dijkstra,因此它可以用队列实现。

dijkstra 的具体实现:

  • 将所有点分为两类(黑点 / 白点),分别代表已确定 / 未确定最短路的点。

  • 每次在白点中选取与起点距离最近的点 \(u\) 染黑,并对所有 \(u \to v\) 进行松弛操作。

其中,距离取 \(\min\) 的操作若直接找是 \(O(n^2)\) 的,套个堆就能做到 \(O(n \log n)\)。

dijkstra 的理论依据(以下简称 引理):

  • 在一张仅有正边权的图中,对于一白点 \(u\),若它在 dijkstra 中被选中了,则一定不存在另一白点 \(v\),使得 \(dis_{s,v}+dis_{v,u}<dis_{s,u}\) 更短(\(s\) 为起点,\(dis_{u,v}\) 表示 \(u,v\) 之间的最短路)。

  • 证明:

    采用反证法。

    假设存在不同于 \(u\) 的一白点 \(v\),使得 \(dis_{s,v}+dis_{v,u}\) 比 \(dis_{s,u}\) 更短,

    因为 \(u\) 在 dijkstra 中被选上了,根据 dijkstra 的实现过程,可得 \(dis_{s,u}<dis_{s,v}\),

    又因图中仅有正边权,所以有 \(dis_{s,u}<dis_{s,v}+dis_{v,u}\),这与假设不符,命题得证。

    证毕

dijkstra 的注意事项:

  • dijkstra 无法用于正负交替边权(全负边权可以转正数后跑)。

  • dijkstra 无法跑最长路。

  • 以上均可用 引理 来解释,在此不再赘述。

T1

brute-force dijkstra 板子。

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+5,M=5e5+5;
int n,m,s;
int dis[N];
bool vis[N];
struct node{ int v,w; };
vector<node> G[M];

void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int mini=1e9,id=0;
		for(int j=1;j<=n;j++)
			if(mini>dis[j]&&!vis[j]) mini=dis[j],id=j;
		vis[id]=1;
		for(node j:G[id])
			if(dis[j.v]>dis[id]+j.w)
				dis[j.v]=dis[id]+j.w;
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++) cout<<(dis[i]==0x3f3f3f3f?2147483647:dis[i])<<' ';
	return 0;
} 

T2

堆优化 dijkstra 板子。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5,M=2e5+5;
int n,m,s;
int dis[N];
bool vis[N];
struct Edge{ int v,w; };
struct Node{
	int u,w;
	bool operator < (const Node &b) const{
		return w>b.w;
	}
};
vector<Edge> G[M];

inline int read() {
	int x = 0, f = 1; char ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline void write(int x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	priority_queue<Node> pq;
	pq.push({s,0});
	while(!pq.empty()){
		Node cur=pq.top(); pq.pop();
		if(vis[cur.u]) continue; vis[cur.u]=1;
		for(Edge j:G[cur.u])
			if(dis[j.v]>dis[cur.u]+j.w)
				dis[j.v]=dis[cur.u]+j.w,
				pq.push({j.v,dis[j.v]});
	}
}

signed main(){
	n=read(),m=read(),s=read();
	for(int i=1,u,v,w;i<=m;i++){
		u=read(),v=read(),w=read();
		G[u].push_back({v,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++) write(dis[i]),putchar(' ');
	return 0;
} 

T3

无向图上的堆优化 dijkstra 板子。

#include<bits/stdc++.h>
using namespace std;

int n,m,s,t;
int dis[3031];
bool vis[3031];
struct Edge{ int v,w; };
struct Node{ 
	int u,w;
	bool operator < (const Node &b) const{
		return w>b.w;
	} 
};
vector<Edge> G[7031];

void dijkstra(){
	memset(dis,0x3f,sizeof(dis)),dis[s]=0;
	priority_queue<Node> pq; pq.push({s,0});
	while(!pq.empty()){
		Node now=pq.top(); pq.pop();
		if(vis[now.u]) continue; vis[now.u]=1;
		for(auto i:G[now.u]){
			if(dis[i.v]>dis[now.u]+i.w&&i.v!=now.u)
				dis[i.v]=dis[now.u]+i.w,
				pq.push({i.v,dis[i.v]});
		}
	}
}

int main(){
	cin>>n>>m>>s>>t;
	for(int i=1,u,v,w;i<=m;i++)
		cin>>u>>v>>w,
		G[u].push_back({v,w}),
		G[v].push_back({u,w});
	dijkstra();
	cout<<dis[t];
	return 0;
}

T4

\(2 \times n\) 遍 dijkstra 即可。

似乎有更优做法,但是我先咕着。

#include<bits/stdc++.h>
using namespace std;

int n,m,ans;
int dis[3031];
bool vis[3031];
struct Edge{ int v,w; };
struct Node{ 
	int u,w;
	bool operator < (const Node &b) const{
		return w>b.w;
	} 
};
vector<Edge> G[7031];

void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis)),dis[s]=0;
	priority_queue<Node> pq; pq.push({s,0});
	while(!pq.empty()){
		Node now=pq.top(); pq.pop();
		if(vis[now.u]) continue; vis[now.u]=1;
		for(auto i:G[now.u]){
			if(dis[i.v]>dis[now.u]+i.w&&i.v!=now.u)
				dis[i.v]=dis[now.u]+i.w,
				pq.push({i.v,dis[i.v]});
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++) 
		cin>>u>>v>>w,G[u].push_back({v,w});
	for(int i=2;i<=n;i++)
		dijkstra(1),ans+=dis[i],
		dijkstra(i),ans+=dis[1];
	cout<<ans;
	return 0;
}

T5

容易发现开关初始状态边权为 \(0\),其余边权均为 \(1\)。

于是如此建图跑 dijkstra 即可。

#include<bits/stdc++.h>
using namespace std;

int n,a,b,ans;
int dis[131];
bool vis[131];
struct Edge{ int v,w; };
struct Node{ 
	int u,w;
	bool operator < (const Node &b) const{
		return w>b.w;
	} 
};
vector<Edge> G[10031];

void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis)),dis[s]=0;
	priority_queue<Node> pq; pq.push({s,0});
	while(!pq.empty()){
		Node now=pq.top(); pq.pop();
		if(vis[now.u]) continue; vis[now.u]=1;
		for(auto i:G[now.u]){
			if(dis[i.v]>dis[now.u]+i.w&&i.v!=now.u)
				dis[i.v]=dis[now.u]+i.w,
				pq.push({i.v,dis[i.v]});
		}
	}
}

int main(){
	cin>>n>>a>>b;
	for(int i=1,k;i<=n;i++){
		cin>>k;
		for(int j=1,v;j<=k;j++)
			cin>>v,G[i].push_back({v,(j==1?0:1)});
	}
	dijkstra(a),cout<<(dis[b]==0x3f3f3f3f?-1:dis[b]);
	return 0;
}

T6

边权设为 \(1-w \times 0.01\),倒序从 \(B\) 推算出 \(A\) 即可。

#include<bits/stdc++.h>
using namespace std;

int n,m,a,b,ans;
double dis[2031];
bool vis[2031];
struct Edge{ int v; double w; };
struct Node{ 
	int u; double w;
	bool operator < (const Node &b) const{
		return w>b.w;
	} 
};
vector<Edge> G[200031];

void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n+1;i++) dis[i]=2147483647.0;
	dis[s]=100.0;
	priority_queue<Node> pq; pq.push({s,100.0});
	while(!pq.empty()){
		Node now=pq.top(); pq.pop();
		if(vis[now.u]) continue; vis[now.u]=1;
		for(auto i:G[now.u]){
			if(dis[i.v]>dis[now.u]/i.w)
				dis[i.v]=dis[now.u]/i.w,pq.push({i.v,dis[i.v]});
		}
	}
}

int main(){
	//freopen("P1576_1.in","r",stdin);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++)
		cin>>u>>v>>w,G[u].push_back({v,1.0-w*0.01}),G[v].push_back({u,1.0-w*0.01});	
	cin>>a>>b;
	dijkstra(b),cout<<setprecision(8)<<fixed<<dis[a];
	return 0;
}

标签:Living,pq,int,41,vis,dijkstra,now,Dream,dis
From: https://www.cnblogs.com/XOF-0-0/p/18048831

相关文章

  • Living-Dream 系列笔记 第40期
    T1bf的做法是\(n\)次floyd,实测可以卡过。然后我们发现当点\(u\)为重要点时,当且仅当存在\((a,b)\)使得\(u\)为它们的唯一中转点。于是我们令\(vis_{i,j}\)表示\((i,j)\)的唯一中转点,接着在floyd的松弛操作中若能松弛则更新其为当前中转点\(k\),否则若没有更优......
  • Living-Dream 系列笔记 第39期
    T1一头牛能确定关系,当且仅当它能到达/被到达除自己外的所有牛。于是我们建出有向图,跑floyd传递闭包,然后对于每个点统计他能到达的点数是否为\(n-1\)即可。#include<bits/stdc++.h>usingnamespacestd;intn,m,ans;intdp[131][131];vector<int>G[4531];voidfl......
  • Living-Dream 周考总结 第3期
    Link,第四场没打。T1\(100\),没挂分。\(\operatorname{lcm}(x,y)=\dfrac{x}{\gcd(x,y)}\timesy\)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ //freopen("as01.in","r",stdin); //freopen("as0......
  • Living-Dream 周考总结 第4期
    Link。T1\(100\),没挂分。依题计算即可。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ //freopen("as01.in","r",stdin); //freopen("as01.out","w",stdout); ios::sync_with_stdio(0); ......
  • Living-Dream 周考总结 第1期
    Link。T1依题计算即可,\(O(1)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ ios::sync_with_stdio(0); doublen;cin>>n,n=ceil(n/5.0); cout<<setprecision(2)<<fixed; if(n<=100)cout<<0.58......
  • Living-Dream 周考总结 第2期
    Link,第二场没打。T1\(100\),没挂分。依题计算即可,\(O(1)\)。#include<bits/stdc++.h>usingnamespacestd;doublen,a,b;intmain(){ //freopen("as01.in","r",stdin); //freopen("as01.out","w",stdout); cin>>n>&......
  • SC5412A ,SC5413A|IQ调制器
    产品简介:调制信号带宽400MHz到6GHz、直流160MHz基带信号更多信息请加weixin-pt890111获取SC5413A和SC5412A是400MHz至6GHz直接IQ调制器,可将模拟同相和正交IF或IQ基带直接上变频至RF。每个模块也可以作为单级上变频器运行。直流耦合差分IQ对可以由任何双通道基带源驱动,例如......
  • 541. 反转字符串 II
    voidreversestring(char*s,inthead,inttail){while(head<=tail){chartemp=s[head];s[head]=s[tail];s[tail]=temp;head++;tail--;}}char*reverseStr(char*s,intk){intns=0;while(s......
  • Go语言精进之路读书笔记第41条——有层次地组织测试代码
    聚焦位于测试包内的测试代码该如何组织41.1经典模式—平铺测试函数各自独立,测试函数之间没有层级关系,所有测试平铺在顶层41.2Unit家族模式测试套件(TestSuite)和测试用例(TestCase)41.3测试固件测试固件是一个人造的、确定性的缓解,在这个环境中进行测试,测试结果是可重复的......
  • p4137-solution
    P4137Solutionlink考虑建主席树:权值线段树的叶子维护这个权值最后出现的下标,push_up的时候取\(\min\)。这样一个区间的\(\min\)小于\(k\)意味着有一个权值最后出现的下标小于\(k\),也就是说\(k\)后面没有出现这个权值。也就是说mex就在这个区间内。这样询问的时候......