随笔（最短路）
城市规划 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:153 测试通过:46
NanJing准备开发一片荒地，目前已经规划好了一些居民点，还要建设道路。由于经费问题，现在想在保持任意两点间的距离最短的前提下，用尽可能少的经费把这些点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。现在给出两两居民点间的花费，当然了，花费和路径长度成正比~
第一行是个N<=100，表示N个居民点。
下面是个N*N的矩阵，第i行第j列，表示i到j的花费，可能有负数，表示两地不相连。保证有解。
输出一行为总花费。
3
0 2 1
2 0 3
1 3 0
floyed
#include <stdio.h>#include <string.h>const int MAXN=100;const int MAXINT=10001;int n,dis[MAXN][MAXN],flag[MAXN][MAXN];int main(){ scanf("%d",&n); int k,i,j,temp; for(i=0;i<n;i++) for(j=0;j<n;j++) { scanf("%d",&dis[i][j]); if(dis[i][j]<0) dis[i][j]=MAXINT; } for(i=0;i<n;i++) for(j=0;j<n;j++) flag[i][j]=1; for(k=0;k<n;k++) for(i=0;i<n;i++) { if(i==k) continue; for(j=0;j<n;j++) { if(k==j)continue; temp=dis[k][j]+dis[i][k]; if(temp<=dis[i][j]){ flag[i][j]=0; dis[i][j]=temp; } } } int ans=0; for(i=0;i<n;i++)for(j=i+1;j<n;j++) if(flag[i][j]) ans+=dis[i][j]; printf("%d\n",ans); return 0;}
#include<iostream>#include<algorithm>using namespace std;#define MAX 101#define MAX_INT 999999999int 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;}