POJ 1724 ROADS(制限された最短経路DFS/BFS)
标题: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;
}