testA
输入文件:
testA.in 输出文件testA.out
时限2000ms
问题描述：
有一个城市拥有N个节点，被M条有权无向路径连接。现在你要在一个地方(可以在路径上当然也可以在节点上)开设一家咖啡馆，使得所有节点达到这个咖啡馆的最短路里面最大值最小（也就是说离咖啡馆最远的节点距离尽可能得小），求出这个最大值的最小值。
输入描述：
第一行N和M。
第2至M+1行，每行三个整数U,V,W。表示从U到V有一条权值为W的无向边。
输出描述：
一行一个数表示答案。四舍五入至2位小数
数据范围N<=200 , W<=100000 , M<=19900
样例输入：
3
2
1 2 100
2 3 1
样例输出：
50.50
这道题考场上我是直接输出了最小生成树的重心。是当时我误认为在这道题里面，最小生成树可以等效为最短路树。
正解是二分答案，判断是否有任何一条边可以安咖啡馆。
至少A了后觉得这道题的确很简单。
还有以后要注意关于交题前要删注释，小数位数按题目所说的写。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXV 170000
#define MAXE 170000
#define MAXN 900
#define PROB "testA"
#define INF 0x3f3f3f3f
struct Edge
{
int np,val;
Edge *next;
bool flag;
}E[MAXE],*V[MAXV];
int m,n;
int map[MAXN][MAXN];
struct aaa
{
int x,y,d;
}el[MAXE];
int tope=-,topl=-;
void addedge(int x,int y,int z)
{
el[++topl].x=x;
el[topl].y=y;
el[topl].d=z;
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope];
E[++tope].np=x;
E[tope].val=z;
E[tope].next=V[y];
V[x]=&E[tope];
}
void init()
{
int i,j,k;
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
for (k=;k<=n;k++)
{
if (map[j][k]>map[j][i]+map[i][k])
map[j][k]=map[j][i]+map[i][k];
}
}
}
}
pair<int,int> seg[MAXN];
int tops=-,rg;
void set_range(int x)
{
tops=-;
rg=x;
}
void add_seg(int x,int y)
{
tops++;
if (x>y)throw "E";
seg[tops].first=x;
seg[tops].second=y;
}
bool full()
{
int i,x=;
sort(seg,&seg[tops+]);
for (i=;i<=tops;i++)
{
if (x<seg[i].first)return false;
if (x>seg[i].second)continue;
x=seg[i].second+;
}
if (x>rg)return true;
return false;
}
int main()
{ freopen(PROB".in","r",stdin);
// freopen(PROB".out","w",stdout);
int i,j,k,x,y,z;
scanf("%d%d",&n,&m);
memset(map,INF,sizeof(map));
for (i=;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(y,x,z*);
map[x][y]=map[y][x]=min(map[x][y],z*);
}
for (i=;i<=n;i++)map[i][i]=;
init();
int l,r,mid;
l=;r=;
int flag=-;
while (l+<r)
{
mid=(l+r)/;
flag=;
for (i=;i<=topl;i++)
{
set_range(el[i].d);
for (j=;j<=n;j++)
{
x=mid-map[el[i].x][j];
y=mid-map[el[i].y][j];
if (x<&&y<)
{
add_seg(,el[i].d);
break;
}
if (x>=el[i].d||y>=el[i].d)
{
continue;
}
if (x+y>=el[i].d)
{
continue;
}
add_seg(max(,x+),min(el[i].d,el[i].d-y-)); }
if (!full())flag=;
if (flag==)
break;
}
if (flag==)
{
l=mid;
continue;
}
if (flag==)
{
r=mid;
continue;
}
}
double ans=r/2.0;
printf("%.2lf",ans);
return ;
}