题目描述 | OJ链接

题意：①先求任意两点间的最短路径累加和，其中不连通的边权为L ②删除任意一条边,求全局最短路径和的最大值。

解题报告：由于要求[多源最短路][路径和]，我们首先可以想到[Floyed]，但是有删边的操作，所以[Floyed]时间复杂度为O(n*n*n*m), 直接跑dijkstra复杂度为o(n*m*m*logn), 复杂度也很大，所以我们可以使用[最短路树]，只有要删的边在树上时，我们才需要重新跑[dijkstra]，由于树上有n-1条边，所以复杂度为o(n*n*m*logn);

ps:要开long long

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
const int M = 1000;
const long long Inf = 1e12 + 7;
#define LL long long LL l;struct Edge{int u, v, w, id;Edge(int u,int v,int w,int id):u(u),v(v),w(w),id(id){}
};
struct HeapNode{LL dist;int u;bool operator<(const HeapNode& rhs) const{return dist>rhs.dist;}
};
struct Dijkstra{int n, m;vector<Edge> edges;vector<int> G[N];LL d[N], ans, ret, dt[N];bool done[N];int p[N], link[M][N], del[M];void init(int n){memset(dt,0,sizeof(dt));memset(link,0,sizeof(link)); ans=ret=0;this->n=n;for ( int i=1; i<=n; i++ ) G[i].clear();edges.clear();  }void addeage(int u, int v, int w, int id){edges.push_back(Edge(u,v,w,id));m=edges.size();G[u].push_back(m-1);}void dijkstra1(int s){for ( int i=1; i<=n; i++ ) d[i]=Inf, done[i]=p[i]=0;priority_queue<HeapNode> Q;Q.push((HeapNode){
   0,s});d[s]=0;while( !Q.empty() ){HeapNode x=Q.top(); Q.pop();int u=x.u;if( done[u] ) continue;done[u]=1;link[p[u]][s]=1;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];if( d[e.v]>d[u]+e.w ){d[e.v]=d[u]+e.w;p[e.v]=e.id;Q.push((HeapNode){d[e.v],e.v});}}}for ( int i=1; i<=n; i++ ){if( d[i]==Inf ) ans+=l, dt[s]+=l;else ans+=d[i], dt[s]+=d[i];}}LL dijkstra2(int s){for ( int i=1; i<=n; i++ ) d[i]=Inf, done[i]=0;d[s]=0;priority_queue<HeapNode> Q;Q.push((HeapNode){
   0,s});while( !Q.empty() ){HeapNode x=Q.top(); Q.pop();int u=x.u;if( done[u] ) continue;done[u]=1;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];if( del[e.id] ) continue;if( d[e.v]>d[u]+e.w ){d[e.v]=d[u]+e.w;Q.push((HeapNode){d[e.v],e.v});}}}LL tt=0;for ( int i=1; i<=n; i++ ){if( d[i]==Inf ) tt+=l;else tt+=d[i];}   return tt; }
};Dijkstra D;int main(){int n, m;while( scanf("%d%d%lld", &n, &m, &l )==3 ){D.init(n);for ( int i=1; i<=m; i++ ){int u, v, w;scanf("%d%d%d", &u, &v, &w );D.addeage(u, v, w, i);D.addeage(v, u, w, i);}for ( int i=1; i<=n; i++ ) D.dijkstra1(i);// for ( int i=1; i<=n; i++ ) printf("%lld\n", D.dt[i]);/* for ( int i=1; i<=m; i++ ){for ( int j=1; j<=n; j++ ) printf("%d ", D.link[i][j] );printf("\n"); }*/for ( int i=1; i<=m; i++ ){D.del[i]=1;LL tt=0;  for ( int j=1; j<=n; j++ ) if( D.link[i][j] ) tt+=D.dijkstra2(j);else tt+=D.dt[j];// printf("%lld\n", tt);D.del[i]=0;D.ret=max(D.ret,tt);}printf("%lld %lld\n", D.ans, D.ret );}
}