@[Vito_fang](/user/226513) 你没判优先队列是不是空的啊
by WAPER4EVER @ 2020-01-16 10:41:35
@[WAPERVAPES](/user/72419)
我刚才改了一下
```cpp
while(!q1.empty() && book[q1.top().id]==1)
```
还是在while卡住了!
（基础不过关的我）、、
by Vito_fang @ 2020-01-16 14:40:34
@[Vito_fang](/user/226513) 不应该啊，能不能给我发份完整代码看看
by WAPER4EVER @ 2020-01-16 15:14:08
@[WAPERVAPES](/user/72419)
好！！！！
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int N,M,K;
int k1,h1[1010],k2,h2[1010];
struct node1{
int t,n,v;
}e1[10010],e2[10010];
void add(int x,int y,int z)
{
k1++;k2++;
e1[k1].t=x;e1[k1].v=z;e1[k1].n=h1[y];h1[y]=k1;
e2[k2].t=y;e2[k2].v=z;e2[k2].n=h2[x];h2[x]=k2;
}
void readdata()
{
scanf("%d%d%d",&N,&M,&K);
int x,y,z;
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
}
bool book[1010];
int dis[1010];
struct node2
{
int id,dis;
friend bool operator <(node2 a,node2 b)
{
return a.dis>b.dis;
}
};
priority_queue<node2> q1;
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
node2 temp;
dis[1]=0;temp.id=1;temp.dis=0;q1.push(temp);
for(int i=1;i<N;i++)
{
while(!q1.empty() && book[q1.top().id]==1)
{
q1.pop();
printf("&&");
}
printf("^^^");
temp=q1.top();q1.pop();
book[temp.id]=1;
for(int i=h1[temp.id];i;i=e1[i].n)
{
int u=e1[i].t,w=e1[i].v;
if(book[u]==0 && dis[u]>dis[temp.id]+w)
{
dis[u]=dis[temp.id]+w;
node2 t;
t.id=u;t.dis=dis[u];
q1.push(t);
}
}
}
}
int visit[1010];
struct node3
{
int id,step,guess;
friend bool operator <(node3 a,node3 b)
{
return a.step+a.guess>b.step+b.guess;
}
};
priority_queue<node3> q2;
void A_star()
{
int cnt=1;node3 temp;
temp.id=N;temp.step=0;temp.guess=dis[N];
q2.push(temp);
while(!q2.empty())
{
temp=q2.top();q2.pop();
visit[temp.id]++;
if(visit[temp.id]>K)
continue;
if(visit[1]==cnt)
{
printf("%d\n",temp.step);
cnt++;
if(cnt>K)
return;
}
for(int i=h2[temp.id];i;i=e2[i].n)
{
int u=e2[i].t,w=e2[i].v;
node3 t;
t.id=u;t.step=temp.step+w;t.guess=dis[u];
q2.push(t);
}
}
while(visit[1]<K)
{
printf("-1\n");
visit[1]++;
}
return;
}
int main()
{
readdata();
dijkstra();
A_star();
return 0;
}
```
感谢。
by Vito_fang @ 2020-01-16 16:09:46
@[Vito_fang](/user/226513) 您咋知道是您的dij出问题
by WAPER4EVER @ 2020-01-16 16:16:45
@[WAPERVAPES](/user/72419)
因为我把那串代码改过后就ac了
by Vito_fang @ 2020-01-16 16:46:30
@[Vito_fang](/user/226513) emmm，那既然您AC了干嘛要提问呢eee
by WAPER4EVER @ 2020-01-16 18:00:20
@[Vito_fang](/user/226513) 我也不是很清楚你那个为什么会TLE。。
by WAPER4EVER @ 2020-01-16 18:00:44
@[WAPERVAPES](/user/72419)
好吧，还是谢谢你了—w—
by Vito_fang @ 2020-01-16 20:47:02