POJ 2607
2024-08-23 08:27:15
一次FLOYD,再枚举。
注意题目要求的输出是什么哦。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int inf=;
const int MAXN=;
int maze[MAXN][MAXN];
bool house[MAXN];
int dis[MAXN],fire,n; int main(){
int u,v,w;
while(scanf("%d%d",&fire,&n)!=EOF){
memset(house,false,sizeof(house));
for(int i=;i<MAXN;i++){
maze[i][i]=; dis[i]=inf;
for(int j=i+;j<MAXN;j++)
maze[i][j]=maze[j][i]=inf;
}
int station;
for(int i=;i<fire;i++){
scanf("%d",&station);
house[station]=true;
dis[station]=;
}
while(~scanf("%d%d%d",&u,&v,&w)){
maze[u][v]=maze[v][u]=min(w,maze[u][v]);
}
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(maze[i][k]+maze[k][j]<maze[i][j]){
maze[i][j]=maze[i][k]+maze[k][j];
}
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(house[j])
dis[i]=min(dis[i],maze[i][j]);
}
}
// for(int i=1;i<=n;i++)
// cout<<dis[i]<<endl;
int tmp,ans,s=inf;
for(int i=;i<=n;i++){
tmp=;
for(int j=;j<=n;j++){
tmp=max(min(dis[j],maze[i][j]),tmp);
}
if(tmp<s){
s=tmp; ans=i;
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- sharepoint powershell 批量处理匿名访问
- Eclipse 设置SVN忽略文件
- LYDSY模拟赛day3 平均数
- eclipse平台
- 如何修改SharePoint列表条数等阈值
- 锋利的jQuery-3--用js给多选的checkbox或者select赋值
- spring mvc实现修改+删除
- 在JavaScript中实现yield,实用简洁实现方式。
- EditPlus保存文件时不生成其备份文件的方法
- java后台获取国际化资源文件
- 构建maven的web项目时注意的问题
- shell实例练习+详解
- windows+CMake+mingw 搭建c c++开发环境
- android 热修补之andfix实践
- java 新手必看大全
- MySQL源码包编译安装
- Cocos Creator学习二:查找节点和查找组件
- css盒子模型之边框
- Mac charles 抓取https请求,安装证书后还是显示unknown
- KnockoutJs学习笔记(十一)
热门文章
- 杂项-Java:JNI
- Java IO流文件复制/解压的几种方法总结
- javascript事件绑定1-模拟jquery可爱的东西
- Redis配置文件各项参数说明及性能调优
- HTML5标签构成
- SQL Server 检测到基于一致性的逻辑 I/O 错误 pageid 不正确(应为 1:1772,但实际为 0:0)。在文件 &#39;D:\Program Files\Microsoft SQL Ser
- dataGridView 设置
- PDF怎么替换页面,教你一招秒实现
- MAMP PRO mysql无法启动
- javascrip this指向问题深入理解