poj1724 Roads
经过无数TLE，终于让我用超级广搜过了这一题
（这题其实和sicily的1702差不多思路）。这题的主要难点有两个，1.存放图，2.剪枝。由于同一对点有可能有多条边，所以直接用二维数组是不可行的。然后最容易想到的是用邻接表。然后就是搜索了。搜索的话，我是用一个二维数组dist[i][cost]来记录从原点到i这一点耗费为cost时的最短路径。这样一来，最终的结果就是dist[n][]中的最小值。剪枝方法就是：当当前结点的的距离小于dist[][]相应值时，才把结点放入队列里面，当然不能忘记的是当前的金钱耗费不能大于k。但是仅仅这样是不够了。这样只会TLE。整个上午就纠结在如何剪枝上，结果还是没什么收获，就去吃饭&看动漫，看完之后突然灵机一闪，发现可以用一个变量minimum记录d[n][]中的最小值，然后如果当前的距离如果不小于minimum的话，就不能加入扩展队列。加上这个剪枝后，终于AC了～哈哈
后记：
1.这题还可以用拆点+dijkstra+堆的方法，但是还没写过，纯粹是看解题报告看来的＝ ＝。
＝＝＝＝＝＝＝＝＝＝＝分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
#pragma warning(disable:4786)
#include <iostream>
#include <queue>
using namespace std;
#define Max 10000000
int k, n, r, dist[101][10001];
//dist[i][cost]记录从原点到i这一点耗费为cost时的最短路径
struct node
{
int l, t, d;
node *next;
node()
{
next = NULL;
}
}g[101];
struct state
{
int len, d, cost;
};
//state表示从原点到当前结点的距离
void input()
{
int i, s, d, l, t;
node *p;
scanf("%d%d%d", &k, &n, &r);
for (i = 0; i < r; i++)
{
scanf("%d%d%d%d", &s, &d, &l, &t);
if (g[s].next == NULL)
{
g[s].next = new node();
p = g[s].next;
}
else
{
p = g[s].next;
while (p->next != NULL) p = p->next;
p->next = new node();
p = p->next;
}
p->d = d;
p->l = l;
p->t = t;
}
}
int BFS()
{
node *p;
state now, ns;
queue<state> q;
int minimum = Max;
//init
memset(dist, 0x7F, sizeof(dist));
dist[1][0] = 0;
now.d = 1;
now.len = 0;
now.cost = 0;
q.push(now);
while (!q.empty())
{
now = q.front();
q.pop();
if (now.d == n) minimum = minimum > now.len ? now.len : minimum;
for (p = g[now.d].next; p != NULL; p = p->next)
{
ns.d = p->d;
ns.cost = now.cost + p->t;
ns.len = now.len + p->l;
if ((ns.cost <= k) && (ns.len < dist[ns.d][ns.cost]) && (ns.len < minimum))
{
dist[ns.d][ns.cost] = ns.len;
q.push(ns);
}
}
}
return (minimum == Max ? -1 : minimum);
}
int main()
{
int minimum;
input();
minimum = BFS();
cout << minimum << endl;
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
#define Max 10000000
int k, n, r, dist[101][10001];
//dist[i][cost]记录从原点到i这一点耗费为cost时的最短路径
struct node
{
int l, t, d;
node *next;
node()
{
next = NULL;
}
}g[101];
struct state
{
int len, d, cost;
};
//state表示从原点到当前结点的距离
void input()
{
int i, s, d, l, t;
node *p;
scanf("%d%d%d", &k, &n, &r);
for (i = 0; i < r; i++)
{
scanf("%d%d%d%d", &s, &d, &l, &t);
if (g[s].next == NULL)
{
g[s].next = new node();
p = g[s].next;
}
else
{
p = g[s].next;
while (p->next != NULL) p = p->next;
p->next = new node();
p = p->next;
}
p->d = d;
p->l = l;
p->t = t;
}
}
int BFS()
{
node *p;
state now, ns;
queue<state> q;
int minimum = Max;
//init
memset(dist, 0x7F, sizeof(dist));
dist[1][0] = 0;
now.d = 1;
now.len = 0;
now.cost = 0;
q.push(now);
while (!q.empty())
{
now = q.front();
q.pop();
if (now.d == n) minimum = minimum > now.len ? now.len : minimum;
for (p = g[now.d].next; p != NULL; p = p->next)
{
ns.d = p->d;
ns.cost = now.cost + p->t;
ns.len = now.len + p->l;
if ((ns.cost <= k) && (ns.len < dist[ns.d][ns.cost]) && (ns.len < minimum))
{
dist[ns.d][ns.cost] = ns.len;
q.push(ns);
}
}
}
return (minimum == Max ? -1 : minimum);
}
int main()
{
int minimum;
input();
minimum = BFS();
cout << minimum << endl;
return 0;
}
2010年9月18日 18:40
好顶啊...绝对绝对要赞一下...