pku2449 제 K 단락 최단로 + A*

제목: 한 점에서 다른 점까지의 K 단락을 구하세요.만약 기점과 종점이 같다면 처음 기점은 종점에 도달한 것이 아니다.
분석: 최단로를 찾아 SPFA로 직행하면 된다...여기는 제 K 단락입니다. 모든 경로를 찾아내세요.처음에는 DP, dp[i][j]로 i 결점 j의 큰 경로 권한이 얼마인지 표시하려고 했지만 이렇게 하면 검색이 되고 시간이 초과됩니다.차라리 A*로 검색하고 우선순위 대기열로 매번 경로 권한 값의 최소값 + 이 점에서 종점까지의 최단거리의 최소값을 대기열에서 내보냅니다.
몇 번째로 어떤 점에 도착했을 때는 대열에 들어갈 때가 아니라 대열에 들어갈 때로 계산하는 것을 주의해라.각 점에서 종점까지의 최단로를 구하기 시작하고 역그림을 만들고 SPFA를 사용한다...

#include<stdio.h>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;

const int maxn=1100;
const int maxm=110000;
const int INF=0x3fffffff;
struct edge
{
	int u,v,w;
}p0,p1;

vector<edge>e[maxn],e1[maxn];

int dist[maxn],times[maxn],n,m,S,T,K;

bool operator >(edge a,edge b)
{
	return a.w+dist[a.v]>b.w+dist[b.v];
}
priority_queue<edge,vector<edge>,greater<edge> >p;

void SPFA(int s)
{
	int i,j,k,head=0,tail=0,q[maxn*2];
	bool inq[maxn];
	for(i=1;i<=n;i++)
		dist[i]=INF,inq[i]=false;
	dist[s]=0,inq[s]=true;
	q[tail++]=s;
	while(head!=tail)
	{
		k=q[head];
		inq[k]=false;
		head=(head+1)%(2*maxn);
		for(i=0;i<e1[k].size();i++)
		{
			j=e1[k][i].v;
			if(dist[j]>dist[k]+e1[k][i].w)
			{
				dist[j]=dist[k]+e1[k][i].w;
				if(!inq[j])
				{
					inq[j]=true;
					q[tail]=j;
					tail=(tail+1)%(2*maxn);
				}
			}
		}
	}
}
void Search()
{
	int i,now;
	bool tag=false;
	while(!p.empty()) p.pop();
	memset(times,0,sizeof(times));
	p0.v=S,p0.w=0;
	p.push(p0);
	while(!p.empty())
	{
		p0=p.top();
		p.pop();
		if(++times[p0.v]>=K)
		{
			if(p0.v==T)
			{
				if(S!=T||(S==T&×[p0.v]==K+1))//         ，            
				{
					tag=true;
					printf("%d
",p0.w);
					break;
				}
			}
			if(times[p0.v]>K)
				continue;
		}
		now=p0.v;
		for(i=0;i<e[now].size();i++)
		{
			p1.v=e[now][i].v;
			p1.w=e[now][i].w+p0.w;
			p.push(p1);
		}
	}
	if(!tag) printf("-1
");
}
int main()
{
	int i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			e1[i].clear();
			e[i].clear();
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&p0.u,&p0.v,&p0.w);
			e[p0.u].push_back(p0);
			j=p0.u;
			p0.u=p0.v;
			p0.v=j;
			e1[p0.u].push_back(p0);
		}
		scanf("%d%d%d",&S,&T,&K);
		SPFA(T);
		if(dist[S]==INF)
		{
			printf("-1
");
			continue;
		}
		Search();
	}
	return 0;
}