VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

有编程疑问吗?还请到提问专区发帖提问!
搜索
查看: 717|回复: 2

[求助] 一道算法竞赛问题,求前辈找错

[复制链接]
50_avatar_middle
在线会员 海浪_SeaWave 发表于 2017-8-13 12:09:26 | 显示全部楼层 |阅读模式
20驿站币
原题:https://www.luogu.org/problem/show?pid=1462

题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士,他是部落的中坚力量
有一天他醒来后发现自己居然到了联盟的主城暴风城
在被众多联盟的士兵攻击后,他决定逃回自己的家乡奥格瑞玛

题目描述
在艾泽拉斯,有n个城市。编号为1,2,3,...,n。
城市之间有m条双向的公路,连接着两个城市,从某个城市到另一个城市,会遭到联盟的攻击,进而损失一定的血量。
每次经过一个城市,都会被收取一定的过路费(包括起点和终点)。路上并没有收费站。
假设1为暴风城,n为奥格瑞玛,而他的血量最多为b,出发时他的血量是满的。
歪嘴哦不希望花很多钱,他想知道,在可以到达奥格瑞玛的情况下,他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入输出格式
输入格式:
第一行3个正整数,n,m,b。分别表示有n个城市,m条公路,歪嘴哦的血量为b。
接下来有n行,每行1个正整数,fi。表示经过城市i,需要交费fi元。
再接下来有m行,每行3个正整数,ai,bi,ci(1<=ai,bi<=n)。表示城市ai和城市bi之间有一条公路,如果从城市ai到城市bi,或者从城市bi到城市ai,会损失ci的血量。
输出格式:
仅一个整数,表示歪嘴哦交费最多的一次的最小值。
如果他无法到达奥格瑞玛,输出AFK。

样例输入
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
样例输出
10

我的思路是二分出一个消费限制,然后在此消费限制下找到消耗血量的最小值,将其和拥有的血量比较。
找最小值我用了记忆化搜索,我知道可以用SPFA,但是想到这个的时候已经快写完了。
实在是没找到什么错误,求各位前辈指教。

  1. #include <cstdio>
  2. #include <cstring>
  3. using namespace std;

  4. #define MAX(x, y) ((x) > (y) ? (x) : (y))
  5. #define MIN(x, y) ((x) < (y) ? (x) : (y))
  6. #define Clear(x) memset(x, 0, sizeof(x))

  7. struct SRoad {
  8.     int iStart, iEnd;
  9.     long long iLife;
  10.     SRoad * pNext;
  11. };

  12. int iCityTot, iRoadTot;
  13. long long iLifeTot, arrCharge[10010];

  14. SRoad * arrRoad[10010];
  15. SRoad * CreateRoad(int iStart = 0, int iEnd = 0, long long iLife = 0, SRoad * pNext = 0)
  16. {
  17.     SRoad * roadTmp = new SRoad;
  18.     roadTmp->iStart = iStart;
  19.     roadTmp->iEnd = iEnd;
  20.     roadTmp->iLife = iLife;
  21.     roadTmp->pNext = pNext;
  22.     return roadTmp;
  23. }
  24. void AddRoad(int iStart, int iEnd, long long iLife)
  25. {
  26.     if (!arrRoad[iStart])
  27.         arrRoad[iStart] = CreateRoad(iStart, iEnd, iLife);
  28.     else
  29.         arrRoad[iStart] = CreateRoad(iStart, iEnd, iLife, arrRoad[iStart]);
  30. }

  31. long long arrResult[10010];
  32. long long Search(int iStart, long long iLimit)
  33. {
  34.     long long & iResult = arrResult[iStart];
  35.     if (iResult || iStart == iCityTot)
  36.         return iResult;
  37.    
  38.     iResult = 0x3f3f3f3f;
  39.     SRoad * pTmp = arrRoad[iStart];
  40.     while (pTmp)
  41.     {
  42.         if (arrCharge[pTmp->iEnd] <= iLimit)
  43.         {
  44.             long long iTmp = Search(pTmp->iEnd, iLimit) + pTmp->iLife;
  45.             iResult = MIN(iResult, iTmp);
  46.         }
  47.         pTmp = pTmp->pNext;
  48.     }
  49.    
  50.     return iResult;
  51. }

  52. bool Solve(long long iLimit)
  53. {
  54.     Clear(arrResult);
  55.     if (arrCharge[1] > iLimit)
  56.         return false;
  57.     else
  58.         return Search(1, iLimit) <= iLifeTot;
  59. }

  60. int main()
  61. {
  62.     long long iChargeMax = -1;
  63.    
  64.     scanf("%d %d %lld", &iCityTot, &iRoadTot, &iLifeTot);
  65.     for (int i = 1; i <= iCityTot; i++)
  66.     {
  67.         scanf("%lld", &arrCharge[i]);
  68.         iChargeMax = MAX(iChargeMax, arrCharge[i]);
  69.     }
  70.         
  71.     for (int i = 1; i <= iRoadTot; i++)
  72.     {
  73.         int iStart, iEnd; long long iLife;
  74.         scanf("%d %d %lld", &iStart, &iEnd, &iLife);
  75.         
  76.         AddRoad(iStart, iEnd, iLife);
  77.         AddRoad(iEnd, iStart, iLife);
  78.     }
  79.    
  80.     long long iLeft = 0, iRight = iChargeMax + 1, iMid, iAns = 0;
  81.     while (iLeft + 1 < iRight)
  82.     {
  83.         iMid = iLeft + (iRight - iLeft) / 2;
  84.         if (Solve(iMid))
  85.             iAns = iRight = iMid;
  86.         else
  87.             iLeft = iMid;
  88.     }
  89.    
  90.     if (iAns)
  91.         printf("%lld", iAns);
  92.     else
  93.         printf("AFK");
  94.    
  95.     return 0;
  96. }
复制代码
一道算法竞赛问题,求前辈找错
第九个测试点的错误信息是:
错误的答案。
On line 1 column 1, read AFK, expected 74733.        





上一篇:橡皮筋类的使用
下一篇:socket 怎么发送16进制数据的

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你已经在论坛发帖求助,并且从坛友或者管理的回复中解决了问题,请编辑帖子并把分类改成【已解决】

如何回报帮助你解决问题的坛友?可以给对方加【热心】【驿站币】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

50_avatar_middle
ico_lz  楼主| 海浪_SeaWave 发表于 2017-8-13 12:16:12 | 显示全部楼层
我找了两个小时的错误,只发现当城市数和公路数比较大(大概5000以上)的时候,有一定几率出错。

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你已经在论坛发帖求助,并且从坛友或者管理的回复中解决了问题,请编辑帖子并把分类改成【已解决】

如何回报帮助你解决问题的坛友?可以给对方加【热心】【驿站币】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

回复

使用道具 举报

61_avatar_middle
在线会员 2017666 发表于 2017-8-14 17:33:52 | 显示全部楼层
厉害了 我等小菜就看看留个名一道算法竞赛问题,求前辈找错

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你已经在论坛发帖求助,并且从坛友或者管理的回复中解决了问题,请编辑帖子并把分类改成【已解决】

如何回报帮助你解决问题的坛友?可以给对方加【热心】【驿站币】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /1 下一条

QQ
QQ在线咨询
联系电话
13591366679
手机扫一扫 关注本站精彩内容
wxqrcode

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2018-11-16 12:17

Powered by Discuz! X3.4

© 2009-2018 cctry.com

快速回复 返回顶部 返回列表