一些疑惑
  • 板块学术版
  • 楼主int_Hello_world
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/3/26 08:42
  • 上次更新2023/10/23 20:28:15
查看原帖
一些疑惑
696967
int_Hello_world楼主2023/3/26 08:42

萌新初学k短路,想问一下A*函数里的优先队列必须用重载运算符吗?可不可以用pair啊。

还有就是,问一下下面这个代码错在哪了。

题目

#include<bits/stdc++.h>
using namespace std;
inline int read() {                   
	int x=0,f=0;char ch=getchar();                   
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');             
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);   
	return f?-x:x;        
}                      
void print(int x) {          
	if(x<0) putchar('-'),x=-x;       
	if(x>9) print(x/10);           
	putchar(x%10+48);               
}
int tot,s,t,n,m,dis[1023131],head[1231313],Hd[1023131],cnt,Ct,x,y,z,k;
bool vis[1023313],f;
struct node{
	int next,to,w;
}e[1023131],E[1023131];
void add(int u,int v,int w){
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt; 
}
void AD(int u,int v,int w){
	E[++Ct].next=Hd[u];
	E[Ct].to=v;
	E[Ct].w=w;
	Hd[u]=Ct;
}
void dj() {
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	priority_queue<int,vector<pair<int,int > >,greater<pair<int,int> > >q;
	dis[t]=0;
	q.push(make_pair(0,t));
	while(!q.empty()){
		int now=q.top().second; q.pop();
		if (vis[now]) continue;
		vis[now]=1;
		for (int i=Hd[now];i;i=E[i].next) {
			if (dis[E[i].to]>dis[now]+E[i].w) {
				dis[E[i].to]=dis[now]+E[i].w;
				q.push(make_pair(dis[E[i].to],E[i].to));
			}
		}
	}
}	
void A_star(){
    priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
    q.push(make_pair(dis[s],make_pair(0,s)));
	while(!q.empty()) {
	    int now=q.top().second.second;
	    int val=q.top().second.first;
	    q.pop();
	    if (now==t) {
	    	tot++;
	    	if (tot==k) {
	    		cout<<val;
	    		f=1;
	    		return ;
			}
	    	continue;
		}
		for (int i=head[now];i;i=e[i].next) {
			q.push(make_pair(e[i].w+dis[e[i].to]+val,make_pair(e[i].w+val,e[i].to)));
		}
	}
}
signed main(){
    n=read(); m=read();
    for (int i=1;i<=m;++i) {
    	x=read(); y=read(); z=read();
    	add(x,y,z);
    	AD(y,x,z);
	}
    s=read(); t=read(); k=read();
    if (s==t) k++;
    dj();
    A_star();
    if (!f) {
    	cout<<-1;
	}
	return 0;
}
2023/3/26 08:42
加载中...