题目链接 题意：就是说有一个有向图，从一点走到所有其他点的最短距离，把这些最短距离加起来；然后还要把从其他点出发走到这一点的最短距离，加起来；两个和加在一起输出。 代码如下：
#include <bits/stdc++.h> using namespace std; #define inf 1e9 int n, m, dp[1005][1005], a[1005], f[1005] = {0}; inline int read() { int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } void dij() { f[1] = 1; int v; for (int i = 1; i < n; ++i) { int min = inf; for (int j = 1; j <= n; ++j) if (!f[j] && min > a[j]) { min = a[j]; v = j; } f[v] = 1; for (int j = 1; j <= n; ++j) if (!f[j] && a[v] + dp[v][j] < a[j]) a[j] = a[v] + dp[v][j]; } } void over() { for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { int t; t = dp[i][j]; dp[i][j] = dp[j][i]; dp[j][i] = t; } } } int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = inf; } dp[i][i] = 0; } for (int i = 0, u, v, w; i < m; ++i) { u = read(), v = read(), w = read(); dp[u][v] = min(dp[u][v], w); } int ans = 0; for (int i = 1; i <= n; ++i) a[i] = dp[1][i]; dij(); for (int i = 1; i <= n; ++i) { ans += a[i]; } over(); memset(f, 0, sizeof(f)); for (int i = 1; i <= n; ++i) a[i] = dp[1][i]; dij(); for (int i = 1; i <= n; ++i) { ans += a[i]; } cout << ans << endl; return 0; }题解：一开始想用Floyd算法，但是超时了（除非吸氧），然后看了dl的操作还是用的dij，默默地学了一手dij（我好菜），要注意的是要用min判断是不是重复输入了同一条道路，判断比较那一条道路更短。 1.本题为带权有向图；
2.去的时候是一到多，回来的时候是多到一；
3.所以回来的时候如果也是一到多就完美了。
所以，我们就有了一个关键性的突破点：把邻接矩阵倒过来！
转载于这里
