萌新初学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;
}