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

Re:bfs+优先队列 32ms 水过~附a*代码

Posted by xc19881023 at 2016-04-29 18:36:46 on Problem 1724
In Reply To:Re:bfs+优先队列 32ms 水过~ Posted by:xc19881023 at 2016-04-29 18:30:40
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int maxN=105,inf=0x3f3f3f3f;
bool h[maxN];
struct arc
{
	int id,dis,toll;

	arc(int _id,int _dis,int _toll):id(_id),dis(_dis),toll(_toll){}
};
struct node
{
	int id,dis,res;
	node(int _id,int _dis,int _res):id(_id),dis(_dis),res(_res){}

	bool operator <(const node &b)const
	{
		if (dis!=b.dis) return dis>b.dis;		
		return res<b.res;		
	}
};
int K,N,R,dis[maxN];
vector<arc> g[maxN];
void read()
{
	scanf("%d%d%d",&K,&N,&R);
	while (R--)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		g[a].push_back(arc(b,c,d));
	}
}

int astar()
{	
	int p[maxN],q[maxN];
	priority_queue<node> pq;
	pq.push(node(1,0,K));	
	while (!pq.empty())
	{
		node top=pq.top();
		pq.pop();
		h[top.id]=true;
		p[top.id]=top.dis;
		q[top.id]=top.res;
		if (top.id==N) return top.dis;
		for (int i = 0; i < g[top.id].size(); i++)
		{
			arc nxt=g[top.id][i];
			if (top.res<nxt.toll) continue;		
			if (h[nxt.id])
			{
				if(nxt.dis+top.dis>=p[nxt.id]&&top.res-nxt.toll<=q[nxt.id]) continue;
				h[nxt.id]=false;
			}
			pq.push(node(nxt.id,nxt.dis+top.dis,top.res-nxt.toll));		
		}
	}
	return -1;
}

int main()
{
//	freopen("D:\\input.txt","r",stdin);
	read();
	printf("%d\n",astar());
	return 0;
}//ac 16ms

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