http://poj.org/problem?id=1062
哎,弱菜伤感呐,N久前做最短路的题,看了这个题,被等级差搞的没思路,昨天突发奇想,脑残的认为1号节点是等级最高的节点,然后把等级差和1号节点超过m的结点忽略,用Dij求一遍最短路,即是解。 写完,提交,wa了,然后看了discuss,发现这个自己的程序建立在一个错误的前提上(1号节点是等级最高的节点),其实可能其他的结点等级更高,所以把程序改成,对于每个包含1号结点等级的长度为m的区间用一次Dij,然后算出最小值。
#include<iostream>
#include<cmath>
using namespace std;
#define MIN(a,b) a>b?b:a
#define inf 10000000
int abs(int a)
{
return a>0?a:-a;
}
struct node
{
int val,lvl;
};
const int SIZE = 110;
node N[SIZE];
int G[SIZE][SIZE];
int d[SIZE],vis[SIZE];
void init()
{
for(int i=0;i<SIZE;i++)for(int j=0;j<SIZE;j++)G[i][j]=inf;
}
void Dijkstra(int n,int m,int l,int r)
{
int i,j,k,v,min;
for(d[1]=0,vis[1]=0,i=2;i<=n;i++)
{
d[i] = inf,vis[i] = 0;
}//init
for(i=1;i<=n;i++)
{
min = inf;
for(j=1;j<=n;j++)
{
if(!vis[j]&&d[j]<min)
min = d[j],v = j;
}
vis[v] = 1;
for(j=1;j<=n;j++)
{
//cout<<abs(N[j].lvl-N[1].lvl)<<endl;
if(G[v][j]!=inf&&N[j].lvl<=r&&N[j].lvl>=l)
{
d[j] = MIN(d[j],d[v]+G[v][j]);
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int m,n;
while(cin>>m>>n)
{
int num,pos,price;
init();
for(int i=1;i<=n;i++)
{
cin>>N[i].val>>N[i].lvl>>num;
for(int j=0;j<num;j++)
{
cin>>pos>>price;
G[i][pos] = price;
}
}
int l,r;//枚举所有包含1号结点,长为m的区间
int min = inf;
for(l=N[1].lvl,r = l+m;r!=N[1].lvl-1;l--,r--)
{
Dijkstra(n,m,l,r);
for(int i=1;i<=n;i++)
{
min = MIN(min,d[i]+N[i].val);
}
}
cout<<min<<endl;
}
return 0;
}
分享到:
相关推荐
解题者可能使用了栈来存储运算符和操作数,逐步处理逻辑表达式,或者采用了类似Dijkstra的短路评估法来简化表达式并判断其真伪。 在解题报告中,可能会详细解释如何将逻辑表达式转换为后缀表达式,如何利用栈来执行...
#### 2267 *From Dusk till Dawn or: Vladimir the Vampire - 最短路 - **知识点**:最短路径算法。 #### 2289 Jamie's Contact Groups - 网络流 - **知识点**:网络流算法。 #### 2337 Catenyms - 欧拉通路 - ...
第四类是最短路,涵盖了至少三个题目,包括 1062、1125 和 1797 等题目。 第五类是最小生成树,涵盖了至少两个题目,包括 1251 和 2578 等题目。 第六类是最大流,涵盖了至少两个题目,包括 1087 和 1459 等题目。...
* 度限制最小生成树和第K最短路:POJ1639、POJ3216、POJ2446 * 最优比率生成树:POJ2728 * 最小树形图:POJ3164 * 次小生成树 * 无向图、有向图的最小环 三、数据结构 * RMQ:POJ3264、POJ3368 * 并查集的高级应用...
1. 度限制最小生成树和第 K 最短路(poj1639, poj3216, poj2446) 2. 最优比率生成树(poj2728) 3. 最小树形图(poj3164) 4. 次小生成树 5. 无向图、有向图的最小环 三、数据结构 1. RMQ(poj3264, poj3368) 2....
通过对Dijkstra算法的详细介绍及POJ3159 Candies问题的具体分析,我们不仅理解了Dijkstra算法的基本原理及其在解决单源最短路径问题上的应用,还了解了如何利用优先队列优化算法的执行效率。这为我们今后解决类似的...
例如,POJ 3013 "Big Christmas Tree" 是一个基础的最短路问题,通过Dijkstra算法可以解决。对于有负权重的边,A*搜索或Bellman-Ford算法可能是更好的选择。POJ 3463 "Sightseeing" 和 POJ 3635 "full tank?" 是较...
4. **最短路**(Shortest Path) 包括Dijkstra、Bellman-Ford、Floyd等算法,如1062、1125、1797、2253、2679等,其中Bellman-Ford适用于存在负权边的情况。 5. **最小生成树**(Minimum Spanning Tree, MST) ...
1. 最短路(Floyd、Dijkstra、Bellman-Ford) 2. 最小生成树(Prim、Kruskal) 3. 大数(高精度)加减乘除 4. 二分查找 5. 叉乘、判线段相交、凸包 6. BFS、DFS、hash表 7. 数学上的辗转相除、线段交点、多角形面积...
4. **最短路算法**:用于求解网络中的最短路径,如1062、1125、1797和2253,以及使用Bellman-Ford算法的2679。 5. **最小生成树算法**:Prim和Kruskal是两种常用的方法,推荐题目有1251、1258、1789和2485。 6. **...
该算法的主要过程是反复交替进行最短路和最大流的计算,利用 Reduced Cost 缩小了费用范围,提高了算法的效率。 知识点: 1. 最小费用流问题:该问题是指在.Flow Network 中寻找一条从源点 S 到汇点 T 的路径,...
在寻找K短路时,先反向运行SPFA算法计算汇点到所有点的最短距离作为h(x),然后在A*搜索中直接入队,当节点入队次数等于K时得到结果。 POJ3463同样是一个中等难度的题目,情况更为复杂。如果源点S到汇点T的次短路径...
5. **14_1最短路I.ppt & 14_2最短路II.ppt** - 这两个PPT可能详细讲解了图论中的最短路径问题,包括Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等,这些都是解决网络流量、路由计算等问题的关键工具。...
这可以通过结合最短路径算法(如连续最短路算法或ZKW改进版费用流)来解决,目标是找到一条费用最小的路径,使得总的流量达到最大。 6. **模型与方法**: 网络流问题有许多不同的模型,如Model I至VI,它们分别...
这里不能简单地做两次最短路,因为它们之间存在相互影响。通过建立费用流网络,从源点向1号地连边,容量为2,费用为0;从N号地向汇点连边,容量为2,费用为0;每条道路正反方向连边,容量各为1,费用为距离。求解...
- **【HDU 2853】Mining Station on the Sea**:题目中的“最短路+KM”可能是指Dijkstra算法与KMP的结合,解决最短路径问题并涉及字符串匹配。 - **【HDU 3315】Assignment 求 KM 最大时,要求改动最少**、**【HDU ...
2.5.4 最短路问题 2.5.5 最小生成树 2.5.6 应用问题 2.6 数学问题的解题窍门 2.6.1 辗转相除法 2.6.2 有关素数的基础算法 2.6.3 模运算 2.6.4 快速幂运算 2.7 一起来挑战GCJ的题目(1) 2.7.1 Minimum Scalar ...
从最短路、最小生成树到最大流,从并查集、快速查找再到数论、线段树,每个类别都包含了至少几个题目,覆盖了算法的多个层面。这些题目不仅考验着对特定算法的理解,也要求学习者具备将理论应用于实际问题的能力。 ...
1. **最短路算法**: - **Floyd-Warshall**:适用于所有顶点对之间的最短路径。 - **Dijkstra**:单源最短路径,用于非负权重的图。 - **Bellman-Ford**:能处理负权重的边,但效率较低。 2. **最小生成树**: ...