POJ 1724 ROADS(制限された最短経路DFS/BFS)

3248 ワード

标题:n都市があって、都市の間に道路があって、道路は有料で、今Bobは都市1から都市nに行きたいと思っていますが、彼の持っているお金には制限があります.今、Bobに限られたお金の中でn城に着くことができるかどうかを聞いて、できれば最短の経路を出力します.标题:最初はvectorで図を作り、果敢にTLE・・.尾部から隣接点を追加したせいか.
#include <vector>
#include <iostream>
using namespace std;

#define N  10005
#define INF 99999

struct Edge
{
	int v, len, cost, next;
} edge[N];

int vis[101], head[N];
int ans, k, n, r;

void dfs ( int u, int len, int money )
{
	if ( len >= ans )
		return;

	if ( u == n )
	{
		ans = len;
		return;
	}

	for ( int i = head[u]; i ; i = edge[i].next )
	{
		if ( !vis[edge[i].v] &&  money >= edge[i].cost )
		{
			vis[edge[i].v] = true;
	        dfs ( edge[i].v, len + edge[i].len, money-edge[i].cost );
		    vis[edge[i].v] = false;
		}
	}
}


int main()
{
	int u, v, l, c;
	memset(vis,0,sizeof(vis));
	memset(edge,0,sizeof(edge));
	memset(head,0,sizeof(head));

	scanf("%d%d%d",&k,&n,&r);
	int i = 0;
	while ( r-- )
	{
		scanf("%d%d%d%d",&u,&v,&l,&c);
		i++;
		edge[i].v = v;
		edge[i].len = l;
		edge[i].cost = c;
		edge[i].next = head[u];
		head[u] = i;
	}
	
	ans = INF;
	vis[1] = true;
	dfs ( 1, 0, k );
	if ( ans == INF ) printf("-1
"); else printf("%d
",ans); return 0; }
#include <queue>
#include <iostream>
using namespace std;

#define N  10005

struct Edge
{
	int v, len, cost, next;
} edge[N];

struct Node
{
	int v, len, cost;
	friend bool operator<(Node a, Node b)
	{
        return a.len > b.len;
	}
} node[N];

int head[N];
int k, n, r;
priority_queue<Node> que; /*                    */

int BFS()
{	
	Node now, next;
	now.cost = 0;
	now.len = 0;
	now.v = 1;
	que.push(now);
	while ( ! que.empty () )
	{
		now = que.top ();
		que.pop();
		if ( now.v == n )
			return now.len;
		for ( int i = head[now.v]; i; i = edge[i].next )
		{
			if ( edge[i].cost + now.cost <= k )
			{
				next.v = edge[i].v;
				next.len = edge[i].len + now.len;
				next.cost = edge[i].cost + now.cost;
				que.push(next);
			}
		}
	}
	return -1;
}


int main()
{
	int u, v, l, c;
	scanf("%d%d%d",&k,&n,&r);

	int i = 0;
	memset(head,0,sizeof(head));

	while ( r-- )
	{
		scanf("%d%d%d%d",&u,&v,&l,&c);
		i++;
		edge[i].v = v;
		edge[i].len = l;
		edge[i].cost = c;
		edge[i].next = head[u];
		head[u] = i;
	}
	
	int ans = BFS();
	if ( ans == -1 ) printf("-1
"); else printf("%d
",ans); return 0; }