这道题我本来是建立多层图然后跑dijkstra来解决，但是由于N=5000，所以会包空间导致RE或者MLE，注意到其实这道题是从1到n都来一遍，其实就可以考虑k-1和k的关系，k在k-
1的基础上面跑最短路，跑完了之后我们对比传送门的两个点到1的距离，这样它可以更新新的最短路。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
int n,m,k;
int s,t;
struct edge
{int to,cost;
};
vector<edge> g[N];
long long d[N];
void add(int u,int v,int cost)
{edge e;e.cost=cost;e.to=v;g[u].push_back(e);
}
priority_queue< P,vector<P>,greater<P> > q;
int vis[N];
void dijkstra(int s)
{for(int i=1;i<=n;i++) q.push(P(d[i],i)),vis[i]=0;q.push(P(0,s));while(!q.empty()){P now=q.top();q.pop();int v=now.second;if(d[v]<now.first) continue;for(int i=0;i<g[v].size();i++){edge e=g[v][i];if(d[e.to]>d[v]+e.cost){d[e.to]=e.cost+d[v];q.push(P(d[e.to],e.to));}}}
}
int main()
{cin>>n>>m;for(int i=1;i<=n-1;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);}int U[N],V[N];for(int i=1;i<=m;i++){cin>>U[i]>>V[i];} for(int A=0;A<=n;A++){dijkstra();}return 0;
}
``
以下是正确代码
include <bits/stdc++.h>
define int long long
using namespace std;
const int N=5500,inf=1e18;
int n,m,d[N],dd[N];
struct edge{
int to,w;
edge(int to=0,int w=0):to(to),w(w){}
};
vector
int U[N2],V[N2];
struct node{
int x,y;
node(int x=0,int y=0):x(x),y(y){}
bool operator < (const node& )const{return y>.y;}
};
priority_queue
int vis[N];
void dij(){
for(int i=1;i<=n;i++)Q.push(node(i,d[i])),vis[i]=0;
while(!Q.empty()){
int u=Q.top().x;
Q.pop();
if(vis[u]++)continue;
for(unsigned i=0;i<g[u].size();i++){
int v=g[u][i].to;
if(d[u]+g[u][i].w<d[v]){
d[v]=d[u]+g[u][i].w;
Q.push(node(v,d[v]));
}
}
}
return;
}
signed main(){
cin>>n>>m;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
g[u].push_back(edge(v,w));
g[v].push_back(edge(u,w));
}
for(int i=1;i<=m;i++){
cin>>U[i]>>V[i];
}
for(int i=2;i<=n;i++){
d[i]=inf;
}
for(int T=0;T<=n;T++){
dij();
int ans=0;
for(int i=1;i<=n;i++)dd[i]=d[i],ans+=d[i];
for(int i=1;i<=m;i++){
dd[U[i]]=min(dd[U[i]],d[V[i]]);
dd[V[i]]=min(d[U[i]],dd[V[i]]);
}
for(int i=1;i<=n;i++)d[i]=min(d[i],dd[i]);
printf("%lld\n",ans);
}
return 0;
}
``