unity gwt 河南省普通话考试官网 河南普通话考试报名官网 网络营销视频 less官网 iot系统 js空格符 spark数据清洗 清空input文本框的值 matlab停止运行 idea全局替换 python逻辑运算符 python迭代器 python基本语法 python图形界面开发 java简介 java写入文件 java字符串查找 java实例方法 java获取本机ip java接口的修饰符 java获取url linuxls命令 linux的安装 linuxshell编程 图吧导航怎么样 信息系统项目管理师教程 lol设置 迅雷免费会员号共享 HTML5从入门到精通 数独软件 联想小新键盘灯怎么开 pr书写效果 0x000007a linux解压命令 sql2008r2 调试js 启用宏在哪里设置 接口自动化测试框架
当前位置: 首页 > 学习教程  > 编程语言

PAT 1003 Emergency (25分)

2020/10/8 19:10:47 文章标签:

题目链接:点击这里 题意:作为一个城市的紧急救援队队长,你会得到一张你国家的特殊地图。这张地图显示了由几条道路连接起来的几个分散的城市。地图上标出每个城市的救援队伍数量和每对城市之间的道路长度。当你接到来自其他城市的紧急电话时…

题目链接:点击这里

题意:作为一个城市的紧急救援队队长,你会得到一张你国家的特殊地图。这张地图显示了由几条道路连接起来的几个分散的城市。地图上标出每个城市的救援队伍数量和每对城市之间的道路长度。当你接到来自其他城市的紧急电话时,你的任务是带领你的人尽快到达目的地,同时在路上尽可能多地召集人手。数据保证至少存在一条路径。

思路:题目给出了一个第二标尺(第一标尺是距离),要求在所有最短路径中选择第二标尺最优的一条路径。

新增点权。用 w e i g h t [ u ] weight[u] weight[u] 表示城市 u u u 中的救援队伍数量,并增加一个数组 w [   ] w[\ ] w[ ],令从起点 s s s 到达顶点 u u u 可以召集到的最多人手为 w [ u ] w[u] w[u],初始化时只有 w [ s ] w[s] w[s] w e i g h t [ s ] weight[s] weight[s]、其余 w [ u ] w[u] w[u] 均为 0 0 0

  • d [ u ] + g [ u ] [ v ] < d [ v ] d[u]+g[u][v] < d[v] d[u]+g[u][v]<d[v](即可以使 s s s v v v 的最短距离 d [ v ] d[v] d[v] 更优)时更新 d [ v ] d[v] d[v] w [ v ] w[v] w[v]

  • d [ u ] + g [ u ] [ v ] = = d [ v ] d[u]+g[u][v]==d[v] d[u]+g[u][v]==d[v](即最短距离相同)且 w [ u ] + w e i g h t [ v ] > w [ v ] w[u]+ weight[v]>w[v] w[u]+weight[v]>w[v](即可以使 s s s v v v 的最多人手数更优)时更新 w [ v ] w[v] w[v]

求最短路径条数。只需要增加一个数组 c n t [   ] cnt[\ ] cnt[ ],令从起点 s s s 到达顶点 u u u 的最短路径条数为 c n t [ u ] cnt[u] cnt[u],初始化时只有 c n t [ s ] cnt[s] cnt[s] 1 1 1、其余 c n t [ u ] cnt[u] cnt[u] 均为 0 0 0

  • d [ u ] + g [ u ] [ v ] < d [ v ] d[u]+g[u][v] < d[v] d[u]+g[u][v]<d[v](即可以使 s s s v v v 的最短距离 d [ v ] d[v] d[v] 更优)时更新 d [ v ] d[v] d[v],并让 c n t [ v ] cnt[v] cnt[v] 继承 c n t [ u ] cnt[u] cnt[u]

  • d [ u ] + g [ u ] [ v ] = = d [ v ] d[u]+g[u][v]==d[v] d[u]+g[u][v]==d[v](即最短距离相同)时将 c n t [ u ] cnt[u] cnt[u] 加到 c n t [ v ] cnt[v] cnt[v] 上。

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 510;

int g[N][N], d[N];
bool st[N];
int weight[N], w[N];
int cnt[N];
int n, m, src, dst;

void dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[src] = 0, cnt[src] = 1, w[src] = weight[src];

    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 0; j < n; j++)
            if(!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        
        st[t] = true;
        
        for(int j = 0; j < n; j++)
        {
            if(d[j] > d[t] + g[t][j])
            {
                d[j] = d[t] + g[t][j];
                cnt[j] = cnt[t];
                w[j] = w[t] + weight[j];
            }
            else if(d[j] == d[t] + g[t][j])
            {
                cnt[j] += cnt[t];
                w[j] = max(w[j], w[t] + weight[j]);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &src, &dst);
    for(int i = 0; i < n; i++)  scanf("%d", &weight[i]);
    
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    dijkstra();
    
    printf("%d %d\n", cnt[dst], w[dst]);
    
    return 0;
}

微信公众号《算法竞赛求职》,致力于详细讲解竞赛和求职所涉及到的算法原理和模板。欢迎关注,一起交流进步!


本文链接: http://www.dtmao.cc/news_show_250109.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?