设g(l,r)表示除了[l,r]区间内的边都加上了的情况下的两两最短路矩阵,那么有递推式$\left\{\begin{matrix}\begin{aligned}&g(l,mid)=cal(g(l,r),mid+1,r)\\&g(mid+1,r)=cal(g(l,r),l,mid)\end{aligned}\end{matrix}\right.$,cal(g,l,r)表示将在g矩阵的基础上把[l,r]区间的边加进去后得到的新的最短路矩阵,加边过程仿照Floyed算法有更新公式$g[i][j]=min(g[i][j],g[i][u]+cost(u,v)+g[v][j],g[i][v]+cost(v,u)+g[u][j])$,终止条件为l=r,分治求解即可(其实比起分治我觉得更像是在线段树上dfs)
1 #include
2 using namespace std;
3 typedef long long ll;
4 typedef double db;
5 const int N=100+10,inf=0x3f3f3f3f;
6 #define mid ((l+r)>>1)
7 int g[20][N][N],ans,ans2,L,n,m;
8 struct E {int u,v,c;} e[1010];
9 void cal(int d,int l,int r) {
10 memcpy(g[d],g[d-1],sizeof g[d]);
11 for(int t=l; t<=r; ++t) {
12 int u=e[t].u,v=e[t].v,c=e[t].c;
13 for(int i=1; i<=n; ++i)
14 for(int j=1; j<=n; ++j)
15 g[d][i][j]=min(g[d][i][j],min(g[d][i][u]+c+g[d][v][j],g[d][i][v]+c+g[d][u][j]));
16 }
17 }
18 void solve(int d=0,int l=1,int r=m) {
19 if(l==r) {
20 int c=0;
21 for(int i=1; i<=n; ++i)
22 for(int j=1; j<=n; ++j)c+=g[d][i][j];
23 ans=max(ans,c);
24 return;
25 }
26 cal(d+1,l,mid),solve(d+1,mid+1,r);
27 cal(d+1,mid+1,r),solve(d+1,l,mid);
28 }
29
30 int main() {
31 while(~scanf("%d%d%d",&n,&m,&L)) {
32 ans=ans2=0;
33 for(int i=1; i<=n; ++i)
34 for(int j=1; j<=n; ++j)
35 g[0][i][j]=(i==j)?0:L;
36 for(int i=1; i<=m; ++i)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
37 solve();
38 for(int t=1; t<=m; ++t) {
39 int u=e[t].u,v=e[t].v,c=e[t].c;
40 for(int i=1; i<=n; ++i)
41 for(int j=1; j<=n; ++j)
42 g[0][i][j]=min(g[0][i][j],min(g[0][i][u]+c+g[0][v][j],g[0][i][v]+c+g[0][u][j]));
43 }
44 for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)ans2+=g[0][i][j];
45 printf("%d %d\n",ans2,ans);
46 }
47 return 0;
48 }