原题：
城市规划
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:75 测试通过:13
描述
NanJing准备开发一片荒地，目前已经规划好了一些居民点，还要建设道路。由于经费问题，现在想在保持任意两点间的距离最短的前提下，用尽可能少的经费把这些点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。现在给出两两居民点间的花费，当然了，花费和路径长度成正比~
输入
第一行是个N<=100，表示N个居民点。
下面是个N*N的矩阵，第i行第j列，表示i到j的花费，可能有负数，表示两地不相连。保证有解。
输出
输出一行为总花费。
样例输入
3
0 2 1
2 0 3
1 3 0
样例输出
3
提示
这里建设1到2 和1到3这两条路。
刚拿到这道题还以为是floyd，仔细看看才发现发现原来不是。
题目中说要保证每个顶点之间的距离最短，也就是说在某个源点到其他点的最短路径上的通路必须保留，其余的边可以滤去；
我的第一个想法是不断的调用DIJ把每个点到其他点的最短路求出来，不过这样有的边会被重复加。
后来又有了第二个想法，就是用一个二维矩阵做为标志，如果这条边（u,v)已经被访问过，那么map[u][v]置成1，这样便解决了重复添加的问题。
这样应该对了吧？我当时也是这样认为的，可惜结果不然。
如果两点间有两条最短路同时存在的情况，该怎么办呢？由于DIJ每一次循环都会找到一条最短路径，那么当用这个确定点去更新其他点的信息时，要使用dis[mark]+map[mark][i]<=di[i]而不是<,这样当出现两条或者两条以上的最短路路时会优先选择已经选择过的点，这样便解决了优先权的问题。
好了，经历的这三个步骤，代码终于AC.呵呵 （Wa了四次）
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101
#define MAX_INT 999999999
int mymap[MAX][MAX];
int visit[MAX];
int dis[MAX];
int pre[MAX];
int record[MAX][MAX];
int n;
int Dij_plus(int s)
{
int result=0;
memset(visit,0,sizeof(visit));
memset(pre,0,sizeof(pre));
int i,j;
for(i=1;i<=n;i++)
{
dis[i]=mymap[s][i];
}
visit[s]=1;
int temp=MAX_INT;
int mark;
for(i=1;i<=n;i++)
pre[i]=-1;
for(i=1;i<=n;i++)
{
if(visit[i]!=1&&mymap[s][i]!=MAX_INT)
pre[i]=s;
}
for(j=1;j<=n-1;j++)
{
temp=MAX_INT;
for(i=1;i<=n;i++)
{
if(visit[i]!=1&&dis[i]<temp)
{
temp=dis[i];
mark=i;
}
}
visit[mark]=1;
if(record[pre[mark]][mark]==0)
{
record[pre[mark]][mark]=1;
record[mark][pre[mark]]=1;
result+=mymap[pre[mark]][mark];
}
for(i=1;i<=n;i++)
{
if(visit[i]!=1&&mymap[mark][i]+dis[mark]<=dis[i])
{
dis[i]=mymap[mark][i]+dis[mark];
pre[i]=mark;
}
}
}
return result;
}
int main ()
{
int i,j;
int result=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
int temp;
scanf("%d",&temp);
if(temp<0)
{
mymap[i][j]=MAX_INT;
mymap[j][i]=MAX_INT;
continue;
}
mymap[i][j]=temp;
mymap[j][i]=temp;
}
}
for(i=1;i<=n;i++)
{
result+=Dij_plus(i);
}
printf("%d\n",result);
system("pause");
return 0;
}