Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

AC ~~~~~~~~~~~~~~~~~~~~>>

Posted by ACAccepted at 2019-03-09 10:54:44 on Problem 2449
#include <cstdio>
#include <queue>
using namespace std;

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

int print(int x)
{
	if (x<0)x=-x,putchar('-');
	if (x>9)print(x/10);
	putchar(x%10+48);
}

int print(int x,char c)
{
	print(x);
	putchar(c);
}

const int INF=100000000;
const int MAXN=1010;
const int MAXM=100010;
int n,m,id[2],from,to,k;

struct edge
{
	int v,w,nx;
}set[2][MAXM];
int head[2][MAXN];
int dis[MAXN];
bool vis[MAXN];

struct dij
{
	int id,dis;
	
	bool operator < (const dij tmp) const
	{
		return dis>tmp.dis;
	}
};

struct star
{
	int id,f,g;
	
	bool operator < (const star tmp) const
	{
		if (f==tmp.f)return g>tmp.g;
		return f>tmp.f;
	}
};

inline void Addedge(int cnt,int u,int v,int w)
{
	id[cnt]++;set[cnt][id[cnt]].v=v;set[cnt][id[cnt]].w=w;set[cnt][id[cnt]].nx=head[cnt][u];
	head[cnt][u]=id[cnt];
}

inline void dijkstra(int s)
{
	priority_queue<dij> Q;
	for (int i=1;i<=n;i++)dis[i]=INF;
	dis[s]=0;
	Q.push((dij){s,0});
	struct dij top;
	int u,v,w;
	while (!Q.empty())
	{
		u=Q.top().id;
		Q.pop();
		vis[u]=0;
		for (int k=head[1][u];k>0;k=set[1][k].nx)
		{
			v=set[1][k].v;w=set[1][k].w;
			if (dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if (!vis[v])
				{
					vis[v]=true;
					Q.push((dij){v,dis[v]});
				}
			}
		}
	}
}

inline void init()
{
	int u,v,w;
	n=read();m=read();
	for (int i=1;i<=m;i++)
	{
		u=read();v=read();w=read();
		Addedge(0,u,v,w);
		Addedge(1,v,u,w);
	}
	from=read();to=read();k=read();
	dijkstra(to);
}

inline int A_star(int cnt)
{
	priority_queue<star> Q;
	if (from==to)cnt++;
	Q.push((star){from,0,0});
	struct star top;
	while (!Q.empty())
	{
		top=Q.top();Q.pop();
		if (top.id==to)
			if ((--cnt)==0)
				return top.f;
		for (int k=head[0][top.id];k>0;k=set[0][k].nx)
			Q.push((star){set[0][k].v,top.g+set[0][k].w+dis[set[0][k].v],top.g+set[0][k].w});
	}
	return -1;
}

int main()
{
	init();
	print(A_star(k));
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator