系统性训练,励志刷完挑战程序设计竞赛-代码整理68~103【初级篇】

本文主要是介绍系统性训练,励志刷完挑战程序设计竞赛-代码整理68~103【初级篇】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2014年9月6日,图的方面,我不太懂。就慢慢学吧

/*warshall-floyd
d[i][j]?????i->j??????? 
*/ 
#include<iostream>
using namespace std;
int  V;
const int MAXN=1<<10;
int d[MAXN][MAXN];
void warshall_floyd(){for(int k=0;k<V;k++)for(int i=0;i<V;i++)for(int j=0;j<V;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}
int main(){warshall_floyd();return 0;
}


/*
dijkstra算法,选最小点d更新边,即加边操作
适用于无负权的图问题 */
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=1<<10;
int cost[MAXN][MAXN];//从u->v的权值
int V,d[MAXN],INF=(1<<31)-1; 
bool used[MAXN];
/*
d[v],cost[u][v]来存储 
*/
void dijkstra1(int s){fill(d,d+V,INF);fill(used,used+V,false);d[0]=0;while(true){int v=-1;//选择一个没有使用的最小值的点 for(int u=0;u<V;u++){if(!used[u] &&(v==-1 || d[u] <d[v])) v=u;		}	if(v==-1) break;  //未选择出来 used[v]=true;//更新所有的点的最小距离   更新操作太多,浪费时间 for(int u=0;u<V;u++)d[u]=min(d[u],d[v]+cost[v][u]);}	
}/*
采用邻接表+堆[查找最小值],复杂度ElogV */struct edge{
int to,cost;	
};vector<edge> G[MAXN];
typedef pair<int ,int> P; // first 代表最短距离,second代表顶点编号 void dijkstra2(int s){priority_queue<P, vector<P>, greater<P> > que;fill(d,d+V,INF);que.push(P(0,s)); //初始化while(!que.empty()){P p= que.top(); que.pop();int v=p.second;   //取出编号 if(d[v]<p.first) continue; //检查与d是否是最小的,确定是否更新d for(int i=0;i<G[v].size();i++){  //更新v的连接边 edge e=G[v][i];if(d[e.to]<d[v]+e.cost){d[e.to]=d[v]+e.cost;que.push(P(d[e.to],e.to));  //将更新后的最小边加入que }}		} }int main(){dijkstra1(0);dijkstra2(0);return 0;	
} 


这篇关于系统性训练,励志刷完挑战程序设计竞赛-代码整理68~103【初级篇】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/745347

相关文章

MySQL 迁移至 Doris 最佳实践方案(最新整理)

《MySQL迁移至Doris最佳实践方案(最新整理)》本文将深入剖析三种经过实践验证的MySQL迁移至Doris的最佳方案,涵盖全量迁移、增量同步、混合迁移以及基于CDC(ChangeData... 目录一、China编程JDBC Catalog 联邦查询方案(适合跨库实时查询)1. 方案概述2. 环境要求3.

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码