返回信息流我用的是Dijstra来写， 算出每个点到其他点的路径，其他点以此类推，再比较路径和最小的节点
测试用例都对，自己造了些数据也没问题，就是无法AC
网址：http://10.105.242.83/submission/add/305/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stack>
#include<vector>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
bool vis[51];
int dis[51];
int numNode;
int const maxN = 10000000000;
int arr[51][51];
void Dijstra(int beg,int &minNum,int &minIndex){
dis[beg] = 0;
for(int i = 1;i<=numNode;i++){
int index = -1,minDis = maxN;
for(int j = 1;j<=numNode;j++){
if(vis[j] == false && minDis>dis[j]){
index = j;
minDis = dis[j];
}
}
if(minDis == -1) break;
vis[index] = true;
for(int j = 1;j<=numNode;j++){
if(vis[j] == false && arr[index][j]!=maxN && arr[index][j]+dis[index]<dis[j]){
dis[j] = arr[index][j]+dis[index];
}
}
}
int total = 0;
for(int i = 1;i<=numNode;i++){
if(dis[i] == maxN) total += numNode;
else total += dis[i];
}
if(total<minNum){
minNum = total;
minIndex = beg;
}else if(total == minNum && minIndex>beg){
minNum = total;
minIndex = beg;
}
}
int main(){
int group;
int row,len;
scanf("%d",&group);
int num1,num2;
while(group--){
int minNum = maxN;
int minIndex;
fill(arr[0],arr[0]+51*51,maxN);
scanf("%d %d",&numNode,&row);
for(int i = 0;i<row;i++){
scanf("%d %d",&num1,&num2);
arr[num1][num2] = 1;
arr[num2][num1] = 1;
}
for(int i = 1;i<=numNode;i++){
fill(vis,vis+51,false);
fill(dis,dis+51,maxN);
Dijstra(i,minNum,minIndex);
}
printf("%d\n",minIndex);
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95048同步于 2018/3/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】北邮oj 305. 网络的核-计算机一2014
glucky
2018/3/16镜像同步13 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
还有int const MaxN不要定超过2^31-1哦～ 这段代码里面maxN其实是溢出了...只是刚好溢出的值也比较大所以过了，放到其他的题可能会出问题哦[ema0]
【 在 xcerwww 的大作中提到: 】
: 还有int const MaxN不要定超过2^31-1哦～ 这段代码里面maxN其实是溢出了...只是刚好溢出的值也比较大所以过了，放到其他的题可能会出问题哦
哇，好细心，谢谢。再请教你下，你说“只是刚好溢出的值也比较大所以过了，放到其他的题可能会出问题哦”，这句话是什么意思？
因为10的10次方溢出以后的值我昨天写程序输出好像是几十万还是几百万的样子 所以你的manN其实不是一百亿 而是他溢出后的值（你可以把你程序中的MaxN输出来看看是多少我忘了...）刚好这道题的数据比较小 边权也只是1 所以里面你计算过程中都没有出现比这个maxN大的值 但是换到其他题里面要是计算过程中出现比这个溢出值要大的值你的计算结果就会出错
【 在 glucky 的大作中提到: 】
:
[ema3]明白谢谢哈
【 在 xcerwww (xcer) 的大作中提到: 】
: 因为10的10次方溢出以后的值我昨天写程序输出好像是几十万还是几百万的样子 所以你的manN其实不是一百亿 而是他溢出后的值（你可以把你程序中的MaxN输出来看...
请教一下，北邮OJ上没有讨论区吗？怎么查看别人的代码？遇到不会的该咋办
【 在 glucky 的大作中提到: 】
: 我用的是Dijstra来写， 算出每个点到其他点的路径，其他点以此类推，再比较路径和最小的节点
: 测试用例都对，自己造了些数据也没问题，就是无法AC
: 网址：http://10.105.242.83/submission/add/305/
: ...................
北邮OJ无讨论区 查看别人的代码在提交列表中点击第一列的id即可～
【 在 czp19940223 的大作中提到: 】
: 请教一下，北邮OJ上没有讨论区吗？怎么查看别人的代码？遇到不会的该咋办