题目链接：http://poj.org/problem?id=3268 头一次用邻接矩阵写spfa，真心弱爆了，而且矩阵转置写错了，线性代数是硬伤啊……
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 #define N 1010
10 int e[N][N], n, m, k, x, y, z, tt[N], g[N];
11 bool f[N];
12 queue<int> Q;
13 void init(){
14 for (int i = 0; i <= n; i++) g[i] = (1 << 31 - 1);
15 memset(f, 0, sizeof(f));
16 }
17 void spfa(int ts){
18 g[ts] = 0; f[ts] = 1; Q.push(ts);
19 while (!Q.empty()){
20 int now = Q.front();
21 Q.pop(); f[now] = 0;
22 for (int i = 1; i <= n; i++){
23 if (e[now][i] != 0 && g[i] > g[now] + e[now][i]){
24 g[i] = g[now] + e[now][i];
25 if (!f[i]){Q.push(i); f[i] = 1;}
26 }
27 }
28 }
29 for (int i = 1; i <= n; i++) tt[i] += g[i];
30 }
31 void zz(){
32 for (int i = 1; i <= n; i++)
33 for (int j = 1; j < i; j++){
34 int t = e[i][j]; e[i][j] = e[j][i]; e[j][i] = t;
35 }
36 }
37 int main(){
38 while (~scanf("%d%d%d", &n, &m, &k)){
39 init();
40 memset(tt, 0, sizeof(tt));
41 memset(e, 0, sizeof(e));
42 while (m--){
43 scanf("%d%d%d", &x, &y, &z);
44 e[x][y] = z;
45 }
46 spfa(k);
47 zz();
48 init();
49 spfa(k);
50 int ans = 0;
51 for (int i = 1; i <= n; i++) ans = max(ans, tt[i]);
52 printf("%d\n", ans);
53 }
54 return 0;
55 }
56
|