POJ 2449 A*+最短路

是的 不压行就不会作死，当你调试半天调不对的时候一般是你很sb的随手打错一行你以为肯定不会错的代码，就当锻炼纠错能力了(本质还是菜。。)

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 1005
#define maxm 500005
#define INF 1000000000 
int tot;
struct node
{
	int to,w,nxt;
}e[maxm],re[maxm];
int head[maxn],rhead[maxn];
int d[maxn],vis[maxn],q[maxm*5];
int n,m,k;
struct Node{
	int to,f,g;
	bool operator < (const Node&a)const
	{
		if(a.f==f) return a.g < g;
		return a.f < f;
	}
	Node(int to=0,int f=0,int g=0):to(to),f(f),g(g){}
};
void add(int u,int v,int w)
{
	e[tot].to = v, e[tot].w = w; e[tot].nxt = head[u]; head[u] = tot;
	re[tot].to = u, re[tot].w = w; re[tot].nxt = rhead[v]; rhead[v] = tot;
	tot++;
}
void spfa(int src)
{
	for(int i = 1; i <= n; i++) d[i] = INF;
    memset(vis, 0, sizeof(vis));
    vis[src] = 0;
    int h = 0, t = 1;
    q[0] = src;
    d[src] = 0;
    while(h < t)
    {
        int u = q[h++];
        vis[u] = 0;
        for(int i = rhead[u] ; i != -1; i = re[i].nxt)
        {
            int v = re[i].to;
            int w = re[i].w;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q[t++] = v;
                    vis[v] = 1;
                }
            }
        }
    }
	
}
int Astar(int src,int des)
{
	priority_queue<Node> q;
	if(src==des) k++;
	if(d[src]==INF) return -1;
	q.push(Node(src,d[src],0));
	Node fa;
	while(!q.empty())
	{
		fa = q.top(); q.pop();
		if(fa.to  == des)
		{
			if(--k==0) return fa.g;
		}
		for(int i = head[fa.to]; ~i; i = e[i].nxt) q.push(Node(e[i].to,fa.g+e[i].w+d[e[i].to],fa.g+e[i].w));
		
	}
	return -1;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{	
		int s,t;
		memset(head,-1,sizeof(head)); memset(rhead,-1,sizeof(rhead)); tot = 0;
		for(int i = 1,u,v,w; i <= m; ++i)
		{
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
		}
		scanf("%d%d%d",&s,&t,&k);
		spfa(t);
		printf("%d\n",Astar(s,t));
	}
	return 0;
}