最短路徑。。。。
由於點比較多1000，，如果dijstra算法 o（n^2）肯定超時，這裡用spfa算法。
由於1000點，沒有用鄰接表，內存略大。
算法很簡單，還是正向建圖，逆向建圖，分別求出起點到其他點的最短距離，然後求和，就是從這點出發，然後再回來的的最短距離，最後求出最大值即可。
代碼：
[cpp]
#include<stdio.h>
#define maxN 1001
#define inf 100000000
int n, x, m;
int mat[maxN][maxN]; //正向圖鄰接矩陣
bool flag[maxN][maxN]; //正向圖標志矩陣
int re_mat[maxN][maxN]; //逆向圖鄰接矩陣
bool re_flag[maxN][maxN];//逆向圖標示矩陣
int dis[maxN]; //起點到其他點的最短路徑
int disRes[maxN]; //往返最短路徑和
bool vis[maxN]; //標示那個點在隊列中
int queue[10 * maxN];//spfa隊列
//鄰接矩陣初始化
void Init()
{
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= n; ++ j)
{
mat[i][j] = inf;
flag[i][j] = false;
re_mat[i][j] = inf;
re_flag[i][j] = false;
}
disRes[i] = 0;
}
}
//spfa算法
void spfa(int mat[][maxN], bool flag[][maxN])
{
for (int i = 1; i <= n; ++ i)
{
vis[i] = false;
dis[i] = inf;
//disRes[i] = 0;
}
int head = 0,tail = 1;
dis[x] = 0;
queue[0] = x;
while (head < tail)
{
int u = queue[head];
vis[u] = true;
for (int i = 1; i <= n; ++ i)
{
if (flag[u][i] && dis[i] > dis[u] + mat[u][i])
{
dis[i] = dis[u] + mat[u][i];
if (!vis[i])
{
vis[i] = true;
queue[tail] = i;
tail ++;
}
}
}
vis[u] = false;
head ++;
}
for (int i = 1; i <= n; ++ i)
{
disRes[i] += dis[i];
}
} www.2cto.com
int main()
{
while (scanf("%d%d%d", &n, &m, &x) != EOF)
{ int a, b, c;
int mMax = -1;
Init();
for (int i = 0; i < m; ++ i)
{
scanf("%d%d%d", &a, &b, &c);
mat[a][b] = c;
flag[a][b] = true;
re_mat[b][a] = c;
re_flag[b][a] = true;
}
spfa(mat, flag);
spfa(re_mat, re_flag);
for (int i = 1; i <= n; ++ i)
{
if (mMax < disRes[i])
{
mMax = disRes[i];
}
}
printf("%d\n", mMax);
}
return 0;
}
作者;zhang20072844
