C++14(g++5.4) 解法, 执行用时: 26ms, 内存消耗: 6636K, 提交时间: 2019-12-26 23:18:42

#include<bits/stdc++.h>
using namespace std;


int N;
int M;
long long G[512][512];
struct Edge {
  long long u, v, w;
};
long long F[512];
int Pre[512];
bool vis[512];
long long H[512][512][2];

int main() {
  memset(G, 0x3f, sizeof(G));
  memset(F, 0x3f, sizeof(F));
  cin >> N >> M;
  vector<Edge> edges(M);
  for (auto &e: edges) cin >> e.u >> e.v >> e.w;
  for (auto e: edges) G[e.v][e.u] = G[e.u][e.v] = min(G[e.u][e.v], e.w);
  vis[1] = true;
  for (int i = 1; i <= N; i++)  F[i] = G[1][i], Pre[i] = 1;
  long long tot = 0;
  for (int _i = 2; _i <= N; _i++) {
    int sel = 0;
    for (int i = 1; i <= N; i++) if (!vis[i]) {
      if (F[sel] > F[i]) sel = i;
    }
    int p = Pre[sel];
    tot += F[sel];
    for (int i = 1; i <= N; i++) if (vis[i]) {
      H[i][sel][0] = H[i][p][0], H[i][sel][1] = H[i][p][1];
      if (H[i][sel][0] < F[sel]) H[i][sel][1] = H[i][sel][0], H[i][sel][0] = F[sel];
      else if (H[i][sel][1] < F[sel]) H[i][sel][1] = F[sel];
      H[sel][i][0] = H[i][sel][0], H[sel][i][1] = H[i][sel][1];
    }
    vis[sel] = true;
    for (int i = 1; i <= N; i++) if (!vis[i]) {
      if (F[i] > G[sel][i]) F[i] = G[sel][i], Pre[i] = sel;
    }
  }
  long long ans = 0x3f3f3f3f3f3f;
  for (auto &e: edges) {
    if (e.w > H[e.u][e.v][0]) ans = min(ans, tot + e.w - H[e.u][e.v][0]);
    if (e.w > H[e.u][e.v][1] && H[e.u][e.v][1]) ans = min(ans, tot + e.w - H[e.u][e.v][1]);
  }
  cout << ans << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 4588K, 提交时间: 2020-05-21 10:20:36

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500+10;
ll g[N][N],mincost[N],maxw[N][N],pre[N];
int n,m,v,u,w;
struct edge
{
	int u,v;
	ll w;
}e[N*N];
ll res,tot;
bool vis[N];
int main()
{
	memset(g,0x3f,sizeof(g));
	memset(mincost,0x3f,sizeof(mincost));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
		g[e[i].v][e[i].u]=g[e[i].u][e[i].v]=min(g[e[i].v][e[i].u],e[i].w);
	}
	mincost[1]=0;
	for(int j=1;j<=n;j++)
	{
		int v=-1;
		for(int i=1;i<=n;i++)
		if(!vis[i]&&(v==-1||mincost[i]<mincost[v]))
		v=i;
		int p=pre[v];
		tot+=mincost[v];
		for(int i=1;i<=n;i++)
		{
			if(vis[i])
			{
				maxw[i][v]=maxw[v][i]=max(maxw[i][p],mincost[v]);
			}
		}
		vis[v]=true;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				if(mincost[i]>g[v][i])
				{
					mincost[i]=g[v][i];
					pre[i]=v;
				}
			}
		}
	}
	res=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=m;i++)
	{
		if(e[i].w>maxw[e[i].u][e[i].v])
		res=min(res,tot-maxw[e[i].u][e[i].v]+e[i].w);
	}
	cout<<res<<endl;
	return 0;
}