原題：
城市規劃
時間限制(普通/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;
}