找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2606|回复: 0
收起左侧

[米群网刷题小分队] [PAT-B] 1087. All Roads Lead to Rome

[复制链接]
发表于 12-21-2014 02:56 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 11-7-2016 04:53 PM 编辑

1087. All Roads Lead to Rome

又是dijkstra, dijkstra很强大,可以中途记录很多东西,只要这些东西局部最优能保证全局最优即可。
有时候需要倒过来而满足这个性质。例如:
1018. Public Bike Management



  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <map>

  5. using namespace std;

  6. const int inf = 1000000000;
  7. const int N = 202;

  8. map<string,int> id;
  9. int cost[N],happy[N],bypass[N],num[N],pre[N],n,a[N][N],b[N];
  10. bool mark[N];        
  11. string name[N];
  12. char s[10];

  13. void dijkstra(int s) {
  14.         for (int i = 0; i < n; ++i) {
  15.                 cost【i】 = bypass【i】 = inf;
  16.                 num【i】  = happy【i】 = 0;
  17.                 mark【i】 = false;
  18.         }
  19.         num[s] = 1;
  20.         cost[s] = bypass[s] =  0;
  21.         pre[s] = -1;
  22.         for (int j = 0; j < n; ++j) {
  23.                 int k = -1;
  24.                 for (int i = 0; i < n; ++i) {
  25.                         if ((!mark【i】) && ((k < 0) || (cost【i】 < cost[k]))) {
  26.                                 k = i;
  27.                         }
  28.                 }
  29.                 mark[k] = true;
  30.                 for (int i = 0; i < n; ++i) {
  31.                         if ((!mark【i】) && (a[k]【i】 < inf)) {
  32.                                 int temp = cost[k] + a[k]【i】;
  33.                                 if (temp < cost【i】) {
  34.                                         cost【i】 = temp;
  35.                                         happy【i】 = happy[k] + b【i】;
  36.                                         bypass【i】 = bypass[k] + 1;
  37.                                         num【i】 = num[k];
  38.                                         pre【i】 = k;
  39.                                 }
  40.                                 else if (temp == cost【i】) {
  41.                                         num【i】 += num[k];
  42.                                         int mayhappy = happy[k] + b【i】;
  43.                                         int maybypass = bypass[k] + 1;
  44.                                         if ((mayhappy > happy【i】) || ((mayhappy == happy【i】) && (maybypass < bypass【i】))) {
  45.                                                 happy【i】 = mayhappy;
  46.                                                 bypass【i】 = maybypass;
  47.                                                 pre【i】 = k;
  48.                                         }
  49.                                 }
  50.                         }
  51.                 }
  52.                
  53.         }
  54. }

  55. void print(int x) {
  56.         if (x) {
  57.                 print(pre[x]);
  58.                 printf("->");
  59.         }
  60.         printf("%s",name[x].c_str());
  61. }

  62. int main() {
  63. int m;
  64.         scanf("%d%d%s",&n,&m,s);
  65.         id[name[0] = s] = 0;
  66.         b[0] = 0;
  67.         for (int i = 0; i < n; ++i) {
  68.                 for (int j = 0; j < n; ++j) {
  69.                         a【i】[j] = inf;
  70.                 }
  71.         }
  72.         for (int i = 1; i < n; ++i) {
  73.                 scanf("%s%d",s,&b【i】);
  74.                 id[name【i】 = s] = i;
  75.         }
  76.         for (;m;--m) {
  77.                 scanf("%s",s);
  78.                 int x = id[s];
  79.                 scanf("%s",s);
  80.                 int y = id[s];
  81.                 int z;
  82.                 scanf("%d",&z);
  83.                 a[x][y] = a[y][x] = min(a[x][y],z);
  84.                
  85.         }
  86.         dijkstra(0);
  87.         int x = id["ROM"];
  88.         printf("%d %d %d %d\n",num[x],cost[x],happy[x],happy[x] / bypass[x]);
  89.         print(x);        
  90.         puts("");
  91.         return 0;
  92. }
复制代码




本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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