`
Coco_young
  • 浏览: 125806 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

POJ_1062_最短路

 
阅读更多

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;
}


分享到:
评论

相关推荐

    POJ3295-Tautology

    解题者可能使用了栈来存储运算符和操作数,逐步处理逻辑表达式,或者采用了类似Dijkstra的短路评估法来简化表达式并判断其真伪。 在解题报告中,可能会详细解释如何将逻辑表达式转换为后缀表达式,如何利用栈来执行...

    poj图论题目汇总

    #### 2267 *From Dusk till Dawn or: Vladimir the Vampire - 最短路 - **知识点**:最短路径算法。 #### 2289 Jamie's Contact Groups - 网络流 - **知识点**:网络流算法。 #### 2337 Catenyms - 欧拉通路 - ...

    ACM 比赛 POJ的训练计划,,,非常不错,关键在于坚持

    第四类是最短路,涵盖了至少三个题目,包括 1062、1125 和 1797 等题目。 第五类是最小生成树,涵盖了至少两个题目,包括 1251 和 2578 等题目。 第六类是最大流,涵盖了至少两个题目,包括 1087 和 1459 等题目。...

    ACMer需要掌握的算法讲解 (2).docx

    * 度限制最小生成树和第K最短路:POJ1639、POJ3216、POJ2446 * 最优比率生成树:POJ2728 * 最小树形图:POJ3164 * 次小生成树 * 无向图、有向图的最小环 三、数据结构 * RMQ:POJ3264、POJ3368 * 并查集的高级应用...

    ACMer需要掌握的算法讲解.docx

    1. 度限制最小生成树和第 K 最短路(poj1639, poj3216, poj2446) 2. 最优比率生成树(poj2728) 3. 最小树形图(poj3164) 4. 次小生成树 5. 无向图、有向图的最小环 三、数据结构 1. RMQ(poj3264, poj3368) 2....

    最短路算法.pdf

    通过对Dijkstra算法的详细介绍及POJ3159 Candies问题的具体分析,我们不仅理解了Dijkstra算法的基本原理及其在解决单源最短路径问题上的应用,还了解了如何利用优先队列优化算法的执行效率。这为我们今后解决类似的...

    acm 题目汇总(好东西)

    例如,POJ 3013 "Big Christmas Tree" 是一个基础的最短路问题,通过Dijkstra算法可以解决。对于有负权重的边,A*搜索或Bellman-Ford算法可能是更好的选择。POJ 3463 "Sightseeing" 和 POJ 3635 "full tank?" 是较...

    NOIP NOI 信息学竞赛 ACM-ICPC POJ(北京大学在线评测系统)刷题推荐 OI复习计划 算法大纲

    4. **最短路**(Shortest Path) 包括Dijkstra、Bellman-Ford、Floyd等算法,如1062、1125、1797、2253、2679等,其中Bellman-Ford适用于存在负权边的情况。 5. **最小生成树**(Minimum Spanning Tree, MST) ...

    参加ACM大赛应该准备哪些课程? (2).pdf

    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. **...

    最小费用流的原始对偶 (Primal-Dual) 算法.docx

    该算法的主要过程是反复交替进行最短路和最大流的计算,利用 Reduced Cost 缩小了费用范围,提高了算法的效率。 知识点: 1. 最小费用流问题:该问题是指在.Flow Network 中寻找一条从源点 S 到汇点 T 的路径,...

    图论拾遗(一)题解1

    在寻找K短路时,先反向运行SPFA算法计算汇点到所有点的最短距离作为h(x),然后在A*搜索中直接入队,当节点入队次数等于K时得到结果。 POJ3463同样是一个中等难度的题目,情况更为复杂。如果源点S到汇点T的次短路径...

    2018数据结构理论课.zip

    5. **14_1最短路I.ppt & 14_2最短路II.ppt** - 这两个PPT可能详细讲解了图论中的最短路径问题,包括Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等,这些都是解决网络流量、路由计算等问题的关键工具。...

    网络流_final1

    这可以通过结合最短路径算法(如连续最短路算法或ZKW改进版费用流)来解决,目标是找到一条费用最小的路径,使得总的流量达到最大。 6. **模型与方法**: 网络流问题有许多不同的模型,如Model I至VI,它们分别...

    费用流题解1

    这里不能简单地做两次最短路,因为它们之间存在相互影响。通过建立费用流网络,从源点向1号地连边,容量为2,费用为0;从N号地向汇点连边,容量为2,费用为0;每条道路正反方向连边,容量各为1,费用为距离。求解...

    KM匹配题集

    - **【HDU 2853】Mining Station on the Sea**:题目中的“最短路+KM”可能是指Dijkstra算法与KMP的结合,解决最短路径问题并涉及字符串匹配。 - **【HDU 3315】Assignment 求 KM 最大时,要求改动最少**、**【HDU ...

    挑战程序设计竞赛(第2版)

    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 ...

    UESTC的ACM题目推荐

    从最短路、最小生成树到最大流,从并查集、快速查找再到数论、线段树,每个类别都包含了至少几个题目,覆盖了算法的多个层面。这些题目不仅考验着对特定算法的理解,也要求学习者具备将理论应用于实际问题的能力。 ...

    常用算法 (2).pdf

    1. **最短路算法**: - **Floyd-Warshall**:适用于所有顶点对之间的最短路径。 - **Dijkstra**:单源最短路径,用于非负权重的图。 - **Bellman-Ford**:能处理负权重的边,但效率较低。 2. **最小生成树**: ...

Global site tag (gtag.js) - Google Analytics