题意：
给一个无向图，n个点，m条边，可不连通，可重边，可多余边。两个问题，第一问：求任意点对之间最短距离之和。第二问：必须删除一条边，再求第一问，使得结果变得更大。
思路：
其实都是在求最短路的过程。
第一问可以floyd解决，也可以SSSP解决。注意是任意两个点，（a,b）和(b,a)是不同的，都要算。
第二问要穷举删除每条边，再求第一问。为了降低复杂度，假设用dijkstra求最短路，那么可以利用第一问中所生成的树，共n棵，每棵至多n-1条边，如果穷举的边不在该某树上，那么该树的所有路径长不变，不必计算，否则需要计算。所以需要记录路径，并将整棵树的边集存起来，同时保存每棵树的任意两点路径之和。
用结构体可以解决重边，问题应该不多，要注意各种细节，错了就重新打，也许更快。
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=;
int n, m, l, edge_cnt;
vector<int> vect[N]; struct node
{
int from, to, dis,tag;
node(){};
node(int from,int to,int dis,int tag):from(from),to(to),dis(dis),tag(tag){};
}edge[]; void add_node(int from,int to,int dis,int tag)
{
edge[edge_cnt]=node(from, to, dis, tag);
vect[from].push_back(edge_cnt++);
} int dist[N], vis[N], path[N];
LL dijkstra(int s)
{
memset(dist,0x7f,sizeof(dist));
memset(vis,,sizeof(vis));
for(int i=; i<=n; i++) path[i]=-; priority_queue<pii,vector<pii>,greater<pii> > que;
dist[s]=;
que.push(make_pair(,s)); while(!que.empty())
{
int x=que.top().second;que.pop();
if(vis[x]) continue;
vis[x]=;
for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
if(e.tag> && dist[e.to]>dist[e.from]+e.dis )
{
path[e.to]=vect[x][i];
dist[e.to]=dist[e.from]+e.dis;
que.push(make_pair(dist[e.to], e.to));
}
}
} LL sum=;
for(int i=; i<=n; i++ )
{
if(dist[i]>=INF) sum+=l;//不可达的，按L算
else sum+=dist[i];
}
return sum;
} LL ans1[N];
int cal()
{
memset(ans1,,sizeof(ans1));
LL first=;
unordered_set<int> tree[N];
for(int i=; i<=n; i++)
{
ans1[i]=dijkstra(i);
first+=ans1[i];
//收集边
for(int k=; k<=n; k++)
{
if(path[k]>=)//注意如何初始化
{
tree[i].insert(path[k]);
tree[i].insert(path[k]^);
}
}
}
//另一个问
LL second=;
for(int i=; i<edge_cnt; i+=)
{
edge[i].tag=edge[i+].tag=;
LL sum=;
for(int j=; j<=n; j++)
{
if( tree[j].find(i)==tree[j].end() ) //是点j的树上，要重新算
sum+=ans1[j];
else
sum+=dijkstra(j);
}
second=max(second, sum);
edge[i].tag=edge[i+].tag=;
}
printf("%lld %lld\n", first, second );//仅1个空格
} int main()
{
freopen("input.txt", "r", stdin);
int a, b, c;
while(scanf("%d%d%d", &n, &m, &l)==)
{
edge_cnt=;
memset(edge,,sizeof(edge));
for(int i=; i<=n; i++) vect[i].clear();
for(int i=; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(a==b) continue;
add_node(a,b,c,);
add_node(b,a,c,);
}
cal();
}
return ;
}
AC代码