CCF考试——201712

Wesley13
• 阅读 579

概要

问题描述

  小明和小芳出去乡村玩,小明负责开车,小芳来导航。
  小芳将可能的道路分为大道和小道。大道比较好走,每走1公里小明会增加1的疲劳度。小道不好走,如果连续走小道,小明的疲劳值会快速增加,连续走s公里小明会增加s2的疲劳度。
  例如:有5个路口,1号路口到2号路口为小道,2号路口到3号路口为小道,3号路口到4号路口为大道,4号路口到5号路口为小道,相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口,则总疲劳值为(2+2)2+2+22=16+2+4=22。
  现在小芳拿到了地图,请帮助她规划一个开车的路线,使得按这个路线开车小明的疲劳度最小。

输入格式

  输入的第一行包含两个整数n, m,分别表示路口的数量和道路的数量。路口由1至n编号,小明需要开车从1号路口到n号路口。
  接下来m行描述道路,每行包含四个整数t, a, b, c,表示一条类型为t,连接a与b两个路口,长度为c公里的双向道路。其中t为0表示大道,t为1表示小道。保证1号路口和n号路口是连通的。

输出格式

  输出一个整数,表示最优路线下小明的疲劳度。

样例输入

6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1

样例输出

76

样例说明

  从1走小道到2,再走小道到3,疲劳度为52=25;然后从3走大道经过4到达5,疲劳度为20+30=50;最后从5走小道到6,疲劳度为1。总共为76。

数据规模和约定

  对于30%的评测用例,1 ≤ n ≤ 8,1 ≤ m ≤ 10;
  对于另外20%的评测用例,不存在小道;
  对于另外20%的评测用例,所有的小道不相交;
  对于所有评测用例,1 ≤ n ≤ 500,1 ≤ m ≤ 105,1 ≤ a, b ≤ n,t是0或1,c ≤ 105。保证答案不超过106。   


思路

该题有大路与小路的区别,同时对于小路还有是否连续之说。主要思路是,将大路与小路的款邻接矩阵分开进行存储。在执行迪杰斯特拉算法时,没找到一个顶点时,设置f标志位lag,若为1则前驱为小路,若为0则为大路。对距离数组进行更新时,分别对小路与大路进行判断跟新。


AC代码

#include <iostream>
#include <string.h>
#include <cmath>
#include <vector> 
#include <cstdio>
using namespace std;

typedef long long ll;
const ll INF = 0x7fffffffffffffff;
ll sA[512][512];                //小路的邻接矩阵 
ll bA[512][512];                //大路的邻接矩阵 
int isvisited_sr[512];          //小路访问数组
int isvisited_br[512];          //大路访问数组
ll n,m;
ll ans;     //结果 

//平方函数 
ll Pow2(ll a)
{
    return  a*a;
}


/*  迪杰斯特拉算法
    该题把大路和小路分开判断 
*/ 
ll Dijikstra(ll t)
{   
    vector<ll> sr(sA[t],sA[t]+n);       //第i结点小路的距离矩阵 
    vector<ll> br(bA[t],bA[t]+n);       //第i结点大路的距离矩阵 
    vector<ll> pre_sr(n,INF);           //第i结点小路的邻接矩阵
    for(int i = 0 ; i < n ; i++){
        if(sr[i] < INF){
            pre_sr[i] = sr[i];
            sr[i] *= sr[i];
        } 
    }
    isvisited_br[t] = isvisited_sr[t] = 1;
    while(1){
        ll MinVal = INF,flag = 0,v = -1;
        for(int i = 0 ; i < n ; i++){
            if(!isvisited_br[i] && br[i] < MinVal){
  
  
  //大路 
                flag = 0;
                MinVal = br[v=i];       
            }
            if(!isvisited_sr[i] && sr[i] < MinVal){
  
  
  //小路 
                flag = 1;
                MinVal = sr[v=i];       
            }
        }
        if(v == -1){
            break;
        }
        if(flag == 1){
  
  
  //大路 
            isvisited_sr[v] = 1;
        }else{
  
  
  //小路 
            isvisited_br[v] = 1; 
        }
        for(int i = 0 ; i < n ; i++){
            if(isvisited_sr[i] == 0 && sA[v][i] < INF){
  
  
  //v到i存在一条小路 
                if(flag == 1){
  
  
  //v的前驱是小路 
                    ll len = sr[v] - Pow2(pre_sr[v]) + Pow2(pre_sr[v]+sA[v][i]);
                    if(sr[i] > len || (sr[i] == len && pre_sr[i] > pre_sr[v]+sA[v][i])){
                        sr[i] = len;
                        pre_sr[i] = pre_sr[v]+sA[v][i];
                    }
                }else{
  
  
  //v的前驱是大路 
                    ll len = br[v]+ Pow2(sA[v][i]);
                    if(sr[i] > len || (sr[i] == len && pre_sr[i] > sA[v][i])){
                        sr[i] = len;
                        pre_sr[i] = sA[v][i]; 
                    }
                }
            }
            if(isvisited_br[i] == 0 && bA[v][i] < INF){
  
  
  //v到i存在一条大路 
                if(flag == 1){
  
  
  //v的前驱是小路 
                    ll len = sr[v] + bA[v][i];
                    br[i] = min(len,br[i]); 
                }else{
  
  
  //v的前驱是大路 
                    ll len = br[v] + bA[v][i];
                    br[i] = min(br[i],len); 
                }
            } 
        }
    }
    return min(sr[n-1],br[n-1]); 
}

int main()
{
    while(cin>>n>>m){
        //对数组进行初始化 
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                sA[i][j] = sA[j][i] = INF;
                bA[i][j] = bA[j][i] = INF;
            }
        }

        for(int i = 0 ; i < 512 ; i++){
            isvisited_sr[i] = isvisited_br[i] = 0;
        } 

        //数据输入,对图进行初始化
        for(int i = 0 ; i < m ; i++){
            ll t,a,b,c;
            cin>>t>>a>>b>>c;
            a--,b--;
            if(t == 1){
                sA[a][b] = sA[b][a] = min(c,sA[a][b]);
            }else{
                bA[a][b] = bA[b][a] = min(c,bA[a][b]);
            }
        }
        ans = Dijikstra(0);
        printf("%lld\n",ans);
    }

    return 0;
}

本文分享 CSDN - 追梦者_AIer。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
徐小夕 徐小夕
3年前
《前端算法系列》如何让前端代码速度提高60倍
今天的问题从排序算法入手,来讲解如何根据业务需求,结合金典的算法,来实现js高性能开发。情景老板让小明给公司的20000条数据排个序,但是由于排序的操作会
Karen110 Karen110
3年前
让Python程序自动玩数独游戏,秒变最强大脑!
作者:小小明,博客地址:https://blog.csdn.net/as604049322最近发现有个玩数独游戏的网站:https://www.sudoku.name/indexcn.php游戏界面如下图所示当然这类玩数独游戏的网站很多,现在我们先以该网站为例进行演示。希望能用Python实现自动计算并填好数独游戏!大概效果能像下面这样就好啦玩过的都非常清楚
CuterCorley CuterCorley
3年前
Django+Vue开发生鲜电商平台之8.商品详情页功能实现
不走康庄大道,我自己喜欢做什么要比别人怎么看我更重要。——李彦宏Github和Gitee代码同步更新:;。一、viewsets实现商品详情页商品详情页效果如下:可以看到,左侧有商品轮播图,右侧是商品的详情信息,包括商品名称、商品描述、是否包邮、市场价、本店价、销量、库存量、购物车按钮、收藏按钮,还包括富文本详情和热卖商品等。apps/go
菜园前端 菜园前端
1年前
考考你CSS的选择器权重
原文链接:选择器权重选择器权重划分代表有多个选择器同时选中同一个元素时,应该以谁的为准,这里就会涉及到权重的问题。现实生活举例假设你的好朋友小明和路人小红同时掉水里,你先救谁?那你可能会先救小明,因为小明的优先级/权重比较高。基础案例在同一层级下同一层级代
待兔 待兔
3年前
软件开发外包的优势,哪些企业适合软件开发外包?
软件开发涉及到需求、设计、研发、交付、维护,很多企业并没有软件开发能力与经验,将软件开发项目外包出去成为一种选择。外包出去企业会少走很多冤枉路,那么进行软件开发项目外包的好处有哪些呢?提高企业工作效率专业的软件开发包括了后台开发、前端设计、实施、后期推广维护等各个方面,团队专业,人员齐全,企业把软件应用交给外包公司来做,自己基本不用花费太多精力,而且
李志宽 李志宽
2年前
扒了手机监控木马后台!
0x00楔子近日,小明有了一桩烦心事,扰的他寝食难安。原来是女神的某安卓手机出了怪病,短信收不到,发出去别人也收不到,更可气的是女神用来准备网购的钱都被神秘刷走。当女神满心焦躁翻遍通讯录时,蓦然发现了小明的备注:千斤顶17号电脑、刷机。于是在女神可怜巴巴大眼睛的注视下,小明把胸脯拍的山响,承诺一天搞定。于是,小明拿到了梦寐以求的女神手机。可没想到,后面发生
Stella981 Stella981
3年前
List的Select 和Select().tolist()
List<PersondelpnewList<Person{newPerson{Id1,Name"小明1",Age11,Sign0},newPerson{Id2,Name"小明2",Age12,
Stella981 Stella981
3年前
DevOps背景下的分合之事
DevOps倡导“谁开发,谁运维”和开发运维一体化。那么是不是简单地把开发和运维人员放在一起就完事了呢?01—“插队”的故事小明入职时是运维专员,原来隶属于运维部门,负责某业务线系统的应用维护工作。一旦系统的生产环境出现任何故障,或者业务人员在生产环境上有任何请求,都是由小明所在的运维部门先处理,处理不了的,再联系该系
源码解析Collections.sort ——从一个逃过单测的 bug 说起 | 京东云技术团队
本文从一个小明写的bug开始,讲bug的发现、排查定位,并由此展开对涉及的算法进行图解分析和源码分析。
待兔 待兔
4个月前
很多人讲不明白HTTPS,但是我能
很多人讲不明白HTTPS,但是我能今天我们用问答的形式,来彻底弄明白HTTPS的过程下面的问题都是小明和小丽两个人通信为例可以把小明想象成服务端,小丽想象成客户端1.https是做什么用的?答:数据安全传输用的。2.数据如何安全的传输?答:把数据加密以后,