题目链接：https://vjudge.net/problem/UVA-1416
题解：
这是一个最短路的好题，首先我们考虑如果暴力弗洛伊德，显然时间复杂度不对，如果做n次spfa好像复杂度也不对，所以考虑优化这个暴力。
我们考虑对于一个单源最短路，只有改变了最短路树中的某条边，才需要重新做一次最短路。所以我们不需要对于每条边都重新做最短路，只需要对于在最短路数上的边做，所以时间复杂度就优化成了你】
mn^2log（n）。
实现的时候要用pre数组记下，以i为终点的最短路树的边，实现有点复杂，看一下代码吧。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#define MAXN 10000
#define ll long long
using namespace std;
struct edge{
int first,next,to,quan,id;
}a[MAXN*];
struct heapnode{
int id,x;
bool operator < (const heapnode &h)const{
return h.x<x;
}
};
priority_queue<heapnode> q;
int dis[MAXN],have[MAXN],hh[MAXN],pre[MAXN],n,m,l,inf,num=;
ll t[MAXN]; void addedge(int from,int to,int quan,int id){
a[++num].to=to;
a[num].id=id;
a[num].quan=quan;
a[num].next=a[from].first;
a[from].first=num;
} ll dij(int s,int cant){
memset(dis,,sizeof(dis));inf=dis[];
memset(have,,sizeof(have));
memset(pre,,sizeof(pre));
while(!q.empty()) q.pop();
dis[s]=;q.push((heapnode){s,});
while(!q.empty()){
int now=q.top().id;
q.pop();
if(have[now]) continue;
have[now]=;
for(int i=a[now].first;i;i=a[i].next){
int to=a[i].to,quan=a[i].quan,id=a[i].id;
if(id==cant) continue;
if(dis[to]>dis[now]+quan){
pre[to]=id;
dis[to]=dis[now]+quan;
q.push((heapnode){to,dis[to]});
}
}
}
ll ret=;
for(int i=;i<=n;i++){
if(dis[i]==inf) ret+=l;
else ret+=dis[i];
}
return ret;
} void sovle(int s){
int c=dij(s,);
for(int i=;i<=n;i++) hh[i]=pre[i];
for(int i=;i<=m;i++) t[i]+=c;
for(int i=;i<=n;i++) if(hh[i]) t[hh[i]]+=dij(s,hh[i])-c;
} int main()
{
while(scanf("%d%d%d",&n,&m,&l)!=EOF){
memset(a,,sizeof(a));
memset(t,,sizeof(t));
num=;
for(int i=;i<=m;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z,i),addedge(y,x,z,i);
}
for(int i=;i<=n;i++) sovle(i);
ll ans=;
for(int i=;i<=m;i++) ans=max(ans,t[i]);
printf("%lld %lld\n",t[],ans);
}
return ;
}