| 题目名称 | 4. 双服务点设置 |
|---|---|
| 输入输出 | djsb.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 8 |
| 题目来源 |
 cqw
于2008-02-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：523， 提交：1069， 通过率：48.92% | ||||
 AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
|
AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_ |
100 | 0.000 s | 0.00 MiB | C++ |
 cy |
100 | 0.000 s | 0.00 MiB | C++ |
 521 |
100 | 0.000 s | 0.00 MiB | C++ |
 河北交通广播992大炮来了 |
100 | 0.000 s | 0.00 MiB | C++ |
 rewine |
100 | 0.000 s | 0.00 MiB | C++ |
 Hyoi_iostream |
100 | 0.000 s | 0.00 MiB | C++ |
 郗志芳 |
100 | 0.000 s | 0.00 MiB | C++ |
|
Marshmello |
100 | 0.000 s | 0.00 MiB | C++ |
| 本题关联比赛 | |||
| ctime蒟蒻生日赛 | |||
| 关于 双服务点设置 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
两个服务点必须不一样！
| ||||
|
OrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzO
 空条承太郎&
2021-10-11 20:31
31楼
| ||||
|
我太笨了
 cb
2020-05-04 14:48
30楼
| ||||
|
回复 @梦那边的美好ETMN :
orzorzorzorzorzorzorzorzorzorz orzorzorzorzorzorzorzorzorzorz orzorzorzorzorzorzorzorzorzorz orzorzorzorzorzorzorzorzorzorz 黄XF da lao  666666666666
2018-09-24 18:17
29楼
| ||||
|
[size=100]orz[/size]
| ||||
|
bmb
 真的菜
2017-11-05 18:27
27楼
| ||||
|
#include <iostream>
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; inline int read(){ int num=0,f=1; char c=getchar(); while(!isdigit(c)){if(c=='-') f=-1; c=getchar();} while(isdigit(c)){num=(num<<1)+(num<<3)+(c^48); c=getchar();} return num*f; } #define maxn 500 vector<int>a[maxn],b[maxn]; queue<int>s; int n,m,dis[maxn],diss[maxn],dk[maxn],maxx=127,tt; bool jud[maxn]; inline int in(){ n=read(); m=read(); for(int i=1;i<=m;i++){ int u,v,c; u=read(); v=read(); c=read(); a[u].push_back(v); a[v].push_back(u); b[u].push_back(c); b[v].push_back(c); } } inline int spfa(int x,int y){ memset(jud,0,sizeof(jud)); memset(dis,10,sizeof(dis)); dis[x]=0; s.push(x); while(!s.empty()){ int city=s.front(); s.pop(); int num=a[city].size(); for(int i=0;i<num;i++){ int next=a[city][i]; int next_c=b[city][i]; if(dis[next]>dis[city]+next_c){ dis[next]=dis[city]+next_c; if(!jud[next]){ s.push(next); jud[next]=1; } } } } memset(jud,0,sizeof(jud)); memset(diss,10,sizeof(diss)); diss[y]=0; s.push(y); while(!s.empty()){ int city=s.front(); s.pop(); int num=a[city].size(); for(int i=0;i<num;i++){ int next=a[city][i]; int next_c=b[city][i]; if(diss[next]>diss[city]+next_c){ diss[next]=diss[city]+next_c; if(!jud[next]){ s.push(next); jud[next]=1; } } } } for(int i=0;i<n;i++) dk[i]=min(dis[i],diss[i]); int ha=0; for(int i=0;i<n;i++) ha=max(ha,dk[i]); return ha; } int x,y; inline int work(){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i!=j){ int ans=spfa(i,j); if(maxx>ans){ maxx=ans; x=i,y=j; } } } } } inline int out(){ cout<<min(x,y)<<" "<<max(x,y); } int main(){ freopen("djsb.in","r",stdin); freopen("djsb.out","w",stdout); in(); work(); out(); }  can
2017-10-27 16:41
26楼
| ||||
|
回复 @雪狼 :
？？？  asd
2017-05-15 20:19
24楼
| ||||
|
| ||||
Hyoi_0Koto
zChengYuan【问题描述】
为了进一步普及九年义务教育，政府要在某乡镇建立两所希望小学，该乡镇共有 $n$ 个村庄，村庄间的距离已知，请问学校建在哪两个村庄最好？（好坏的标准是学生就近入学，即在来上学的学生中，以最远的学生走的路程为标准。或者说最远的学生与学校的距离尽可能的小。）
【输入格式】
输入由若干行组成，第一行有两个整数 $n(1\le n\le 100)$ 和 $m(1\le m\le n^2)$；$n$ 表示村庄数，$m$ 表示村庄间道路数。第 $2$ 至 $m+1$ 行是每条路的信息，每行三个整数，为道路的起点、终点和两村庄间距离。（村庄从 $0$ 开始编号）
【输出格式】
两个整数，学校所在村庄编号(如果两个以上村庄都适合建立学校，选择编号小的两个村庄建学校，输出时按编号从小到大输出)。
【样例输入】
6 8 0 2 10 0 4 30 0 5 100 1 2 5 2 3 50 3 5 10 4 3 20 4 5 60
【样例输出】
0 3
【数据约定】
所有边和、及中间结果不超过$int$.
数据中可能会有重边，比如：$0$-$1$之间有$2$条路，$2$条边权值不同。
如果有重边，以最新输入的为准。