#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int maxN=105,inf=0x3f3f3f3f;//最多105个
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;//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 bfs()
{	
	priority_queue<node> pq;
	pq.push(node(1,0,K));//一开始钱是K
	while (!pq.empty())
	{
		node top=pq.top();
		pq.pop();
		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;	//如果付不起过路费的话,直接pass							
			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",bfs());
	return 0;
}

• Re:bfs+优先队列 32ms 水过~ (71) xc19881023 2016-04-29 18:30:40
  • Re:bfs+优先队列 32ms 水过~附a*代码 (1358) xc19881023 2016-04-29 18:36:46