poj 1502 单源最短路径

简介:

一、题目大意

无向图,给出邻接矩阵的下半矩阵,要求源点1,到其他点最短时间(散播整个网络的最短时间)。

二、AC code

明显的单源最短路径

但是还是用了Floyd算法撞撞运气,毕竟是无向图,当然可以对Floyd优化,最后也可以A。

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <cassert>
#include <time.h>
#include <queue>
//#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <sstream>
#define INF 0x3f3f3f3f

using namespace std;

template <class Type>
Type stringToNum(const string& str)
{
    istringstream iss(str);
    Type num;
    iss >> num;
    return num;    
}

//======================================================

#define MAXN 102
int map[MAXN][MAXN];

int main()
{
    //freopen("input.txt","r",stdin);

    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {

            string s;
            cin>>s;

            int tmp = INF;
            if(s != "x"){
                tmp = stringToNum<int > (s);
            }

            map[j][i] = map[i][j] = tmp;
        }
    }

    //floyd
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {

                map[j][i] = map[i][j] = min(map[i][j],map[i][k]+map[k][j]);
            }
        }
    }

    int time = -1;
    for (int i = 2; i <= n ; ++i) {
        time = time > map[1][i]? time : map[1][i];
    }
    cout<<time<<endl;

    return 0;
}

dijkstra:

重定向忘记删掉,WA一次,甚是可惜

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <cassert>
#include <time.h>
#include <queue>
//#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <sstream>
#define INF 0x3f3f3f3f

using namespace std;

template <class Type>
Type stringToNum(const string& str)
{
    istringstream iss(str);
    Type num;
    iss >> num;
    return num;    
}

//======================================================

#define MAXN 102
int map[MAXN][MAXN];
bool visited[MAXN];

void update(int minPos,int n) {

    for (int i = 1; i <= n; ++i) {

        if( !visited[i] && map[1][i] > map[1][minPos] + map[minPos][i] )
            map[i][1] = map[1][i] = map[1][minPos] + map[minPos][i];
    }
}

void dijkstra(int n) {

    visited[1] = 1;
    while(1) {

        int tmpMin = INF;
        int minPos = -1;
        for (int i = 2; i <= n; ++i) {

            if( !visited[i] && tmpMin > map[1][i] ) {
                //have not been visited && smaller

                tmpMin = map[1][i];
                minPos = i;
            }
        }

        if( -1 == minPos )
            break;

        visited[minPos] = 1;
        update(minPos,n); //update the map, if it's shorter to get through minPos
    }
}

int main()
{
    //freopen("input.txt","r",stdin);

    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {

            string s;
            cin>>s;

            int tmp = INF;
            if(s != "x"){
                tmp = stringToNum<int > (s);
            }

            map[j][i] = map[i][j] = tmp;
        }
    }

    dijkstra(n);

    int time = -1;
    for (int i = 2; i <= n ; ++i) {
        time = time > map[1][i]? time : map[1][i];
    }
    cout<<time<<endl;

    return 0;
}
相关文章
|
5月前
|
存储 前端开发 数据可视化
Postman vs. Apifox 用于 API 测试全面对比
寻找一款可靠的 API 测试工具?这份对比分析将深入探讨 Postman 和 Apifox 的功能和特性。了解哪款工具最适合您的 API 测试需求。
|
11月前
|
算法 索引
让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)
`HashMap`的`resize()`方法主要用于数组扩容,包括初始化或加倍数组容量。该方法首先计算新的数组容量和扩容阈值,然后创建新数组。接着,旧数组中的数据根据`(e.hash & oldCap)`是否等于0被重新分配到新数组中,分为低位区和高位区两个链表,确保数据迁移时的正确性和高效性。
201 3
|
11月前
|
消息中间件 存储 Kafka
面试题:Kafka如何保证高可用?有图有真相
面试题:Kafka如何保证高可用?有图有真相
320 0
|
人工智能 自然语言处理 算法
入局AI新赛道,这块敲门砖你get了吗?
入局AI新赛道,这块敲门砖你get了吗?
209 0
|
存储 安全 搜索推荐
宜搭版本调整通知(更新)
宜搭一直致力于为用户提供更优质的使用体验。为了更好地满足广大用户需求,宜搭将于2023年7月3日进行版本调整。
12556 3
宜搭版本调整通知(更新)
|
SpringCloudAlibaba Java Nacos
Nacos报错问题之服务端注册的时候返回404如何解决
Nacos是一个开源的、易于部署的动态服务发现、配置管理和服务管理平台,旨在帮助微服务架构下的应用进行快速配置更新和服务治理;在实际运用中,用户可能会遇到各种报错,本合集将常见的Nacos报错问题进行归纳和解答,以便使用者能够快速定位和解决这些问题。
1700 1
|
SQL 关系型数据库 MySQL
MYSQL数字函数实操宝典:场景化SQL语句一网打尽
本文作为MYSQL数字函数实操宝典,通过丰富的场景化SQL语句实例,一网打尽了MYSQL中常用的数字函数。我们深入探讨了ROUND函数在金额四舍五入、评分计算等场景的应用,展现了其在确保数据准确性和展示规范性方面的重要性。同时,FLOOR函数在分页处理、价格计算等实际案例中的灵活运用,也体现了其在向下取整方面的优势。此外,CEIL函数在分页处理、费用计算等方面的应用案例,充分展示了其向上取整的功能特点。这些实用案例不仅有助于读者更好地理解MYSQL数字函数的工作原理,更为开发者在实际开发中提供了有价值的参考
207 8
|
Web App开发 算法 前端开发
备战大厂,彻底搞懂垃圾回收机制底层原理(下)
备战大厂,彻底搞懂垃圾回收机制底层原理(下)
135 0
|
XML 小程序 前端开发
微信小程序接入微信支付流程
微信小程序接入微信支付流程
微信小程序接入微信支付流程