POJ-1502-MPI Maelstrom

POJ-1502-MPI Maelstrom

链接:https://vjudge.net/problem/POJ-1502

题意:

n个点,从1号向开始选择任意个结点发送信息,下一个结点接收到信息后可再向任意个结点发送。

同时发送信息有时间代价。代价有邻接矩阵给出。只给出坐下全部,x为不连通。

同时为无向的。即a->b == b->a。

求每个结点都接受到信息的最小时间代价。

思路:

Dijkstra,求Dis数组中的最大值

代码:

#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
using namespace std;
const int MAXN = 100+10;
int Map[MAXN][MAXN];
int Dis[MAXN];
int Vis[MAXN];

int main()
{
    int n;
    scanf("%d",&n);

    for (int i = 1;i<=n;i++)
        for (int j = 1;j<=n;j++)
            if (i == j)
                Map[i][j] = 0;
            else
                Map[i][j] = 999999;

    for (int i = 2;i<=n;i++)
        for (int j = 1;j<i;j++)
        {
            string x;
            cin >> x;
            if (x[0] != 'x')
            {
                istringstream iss(x);
                int num;
                iss >> num;
                Map[i][j] = Map[j][i] = num;
            }
        }
    for (int i = 1;i<=n;i++)
        Dis[i] = Map[1][i];
    Vis[1] = 1;
    for (int i = 1;i<=n;i++)
    {
        int w = -1,small = 999999;
        for (int j = 1;j<=n;j++)
            if (Vis[j] == 0&&Dis[j] < small)
            {
                w = j;
                small = Dis[j];
            }
        Vis[w] = 1;
        for (int j = 1;j<=n;j++)
        {
            if (Vis[j] == 0)
            {
                Dis[j] = min(Dis[j],Dis[w]+Map[w][j]);
                //cout << Dis[j] << ' ' << Dis[w] + Map[w][j] << endl;
            }
        }
    }
    int sum = 0;
    for (int i = 2;i<=n;i++)
        sum = max(sum,Dis[i]);
    cout << sum << endl;

    return 0;
}
/*
4
10
x 10
x x 10
 */

  

转载于:https://www.cnblogs.com/YDDDD/p/10274877.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101169.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ride运行报错_chrome OS

    ride运行报错_chrome OShttp://chromedriver.storage.proxy.ustclug.org/index.html下载地址,注意需要与chrome版本对应chromedriver下载解压后,放在chrome安装目录下,查看安装目录chrome://version/最后配置环境变量,chrome安装目录配置在path后重启(我是win10,开始配置在系统变量中重启后无效,后来在用户变量…

  • 一个Django项目:搭建基本自动化运维平台[通俗易懂]

    一个Django项目:搭建基本自动化运维平台[通俗易懂]之前做的一个Python项目,采用了Django的MTV框架搭建,实现的是主机的CMDB平台与作业平台基本功能。基本的搭建步骤:1.确定平台的基本功能有哪些:实现主机的自动添加,删除,修改;实现所管理主机配置信息的监控;实现指定对象的批量管理2.根据上面的功能,设计对应的页面方式,布局,规划如何交互的。:如何执行命令与显示3.根据上面的规划,拟定需要怎样的架构,分别需要几个模块(M…

  • QT5编程入门教程(非常详细)「建议收藏」

    QT5编程入门教程(非常详细)「建议收藏」Qt是一个跨平台的C++框架(C++库),目前最新的版本是Qt5。Qt5还包含了很多小版本,其中推荐Qt5.6或Qt5.9,这两个版本是LTS版本(即长期支持版本),Bug较少,相对稳定。Qt除了支持界面设计(GUI编程),还封装了与网络编程、多线程、数据库连接、视频音频等相关的功能。这套Qt教程以Qt5.9为基础来介绍Qt开发,配有精美的图片以及完整的示例程序,几乎涉及Qt编程的所有模块。注意,本教程不再对C++语法进行介绍,没有C++基础的读者…

  • 安装AdventureWorks2008[通俗易懂]

    安装AdventureWorks2008[通俗易懂]1、设置sqlserver高权限,并重新启动sqlserver服务。2、安装并启动全文服务(SQLFull-textFilterDaemonLauncher)3、启用sqlserver的文件流 FILESTREAM 的权限4、重启服务再连接即可。

  • 进销存ERP源码 小程序源码 APP源码

    进销存ERP源码 小程序源码 APP源码进销存ERP源码+小程序源码+APP源码+H5系统简介:常规管理系统配置 附件管理 个人资料 数据库管理分类管理用于统一管理网站的所有分类,分类可进行无限级分类,分类类型请在常规管理->系统配置->字典配置中添加权限管理管理员管理 管理员日志 角色组会员管理会员管理 会员分组 会员规则进销存管理1、商品管理商品分类商品信息商品单位2、库存管理商品存库库存流水盘点单

  • 新闻专栏~ART让Android更流畅

    新闻专栏~ART让Android更流畅

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号