POJ2449 Remmarguts' Date 第K短路

时间：2020-12-10 13:41:02

POJ2449 比较裸的K短路问题

K短路听起来高大上 实际思路并不复杂

首先对终点t到其他所有点求最短路 即为dist[]

然后由起点s 根据当前走过的距离+dist[]进行A*搜索 第k次到达t即为第K短路

代码也很简单

//数组开的不够 不一定是运行时错误！ 可能也会WA

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<vector>

using namespace std;

typedef long long int LL;

const int maxn=(1e+3)+1,maxm=(1e+5)+1;

vector<int > son[maxn];vector<int >fa[maxn];

int ea[maxm],eb[maxm],len[maxm];

LL dist[maxn];

bool vis[maxn];

typedef pair<int,int>po;

const LL INF=1e+18;

priority_queue<po,vector<po>,greater<po> >q;

int times;

po p[maxn];

struct pi

{

 LL f;

 LL dis;

 int th;

 pi(LL a,LL b,int c)

 	{

 	 f=a;

 	 dis=b;

 	 th=c;

	}

 bool operator<(const pi b)const

 	{

	 if(f==b.f)return dis>b.dis;

 	 return f>b.f;

	}

};

priority_queue<pi>Q;

int main()

{freopen("t.txt","r",stdin);

 int n,m;

 scanf("%d%d",&n,&m);

 for(int i=1;i<=n;i++)

 	{son[i].clear();fa[i].clear();}

 for(int i=1;i<=m;i++)

 	{

 	 int a,b,l;

     scanf("%d%d%d",&a,&b,&l);

	 ea[i]=a;eb[i]=b;len[i]=l;

	 son[a].push_back(i);fa[b].push_back(i);

	}

 int s,t,k;

 scanf("%d%d%d",&s,&t,&k);

 for(int i=1;i<=n;i++)

  	{dist[i]=INF;}

 while(!q.empty())q.pop();

 dist[t]=0;

 for(int i=1;i<=n;i++)

 	p[i]=po(dist[i],i);

 q.push(p[t]);

 memset(vis,0,sizeof(vis));

 while(!q.empty())

 	{

 	 int mark;

	 po now=q.top();

	 q.pop();

 	 mark=now.second;

	 if(vis[mark])continue;

	 vis[mark]=true;

	 for(int i=0;i<fa[mark].size();i++)

	 	{

	 	 int e=fa[mark][i];

	 	 int father=ea[e];

	 	 if(dist[father]>(dist[mark]+len[e]))

		    {dist[father]=dist[mark]+len[e];po np(dist[father],father);q.push(np);}

		}

	}

 while(!Q.empty())Q.pop();

 pi start(dist[s],0,s);

 Q.push(start);

 LL ans=-1;

 if(s==t)k++;

 while(!Q.empty())

 	{

 	 if(dist[s]==INF)break;

 	 pi now=Q.top();

 	 Q.pop();

	 int npo=now.th;

	 if(npo==t)	times++;

	 if(npo==t&&times==k){ans=now.dis;break;}

	 for(int i=0;i<son[npo].size();i++)

	 	{

	 	 int e=son[npo][i];

	 	 int so=eb[e];

	 	 pi ps(now.dis+len[e]+dist[so],now.dis+len[e],so);

	 	 Q.push(ps);

		}

	}

 cout<<ans<<endl;

 return 0;

}

　　

相关文章