原題：
城市規(guī)劃
時間限制(普通/Java):1000MS/3000MS 運行內(nèi)存限制:65536KByte
總提交:75 測試通過:13
描述
NanJing準(zhǔn)備開發(fā)一片荒地，目前已經(jīng)規(guī)劃好了一些居民點，還要建設(shè)道路。由于經(jīng)費問題，現(xiàn)在想在保持任意兩點間的距離最短的前提下，用盡可能少的經(jīng)費把這些點連接起來。需要注意的是并不是任意兩個居民點間都能直接相連。現(xiàn)在給出兩兩居民點間的花費，當(dāng)然了，花費和路徑長度成正比~
輸入
第一行是個N<=100，表示N個居民點。
下面是個N*N的矩陣，第i行第j列，表示i到j的花費，可能有負(fù)數(shù)，表示兩地不相連。保證有解。
輸出
輸出一行為總花費。
樣例輸入
3
0 2 1
2 0 3
1 3 0
樣例輸出
3
提示
這里建設(shè)1到2 和1到3這兩條路。
剛拿到這道題還以為是floyd，仔細(xì)看看才發(fā)現(xiàn)發(fā)現(xiàn)原來不是。
題目中說要保證每個頂點之間的距離最短，也就是說在某個源點到其他點的最短路徑上的通路必須保留，其余的邊可以濾去；
我的第一個想法是不斷的調(diào)用DIJ把每個點到其他點的最短路求出來，不過這樣有的邊會被重復(fù)加。
后來又有了第二個想法，就是用一個二維矩陣做為標(biāo)志，如果這條邊（u,v)已經(jīng)被訪問過，那么map[u][v]置成1，這樣便解決了重復(fù)添加的問題。
這樣應(yīng)該對了吧？我當(dāng)時也是這樣認(rèn)為的，可惜結(jié)果不然。
如果兩點間有兩條最短路同時存在的情況，該怎么辦呢？由于DIJ每一次循環(huán)都會找到一條最短路徑，那么當(dāng)用這個確定點去更新其他點的信息時，要使用dis[mark]+map[mark][i]<=di[i]而不是<,這樣當(dāng)出現(xiàn)兩條或者兩條以上的最短路路時會優(yōu)先選擇已經(jīng)選擇過的點，這樣便解決了優(yōu)先權(quán)的問題。
好了，經(jīng)歷的這三個步驟，代碼終于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;
}