1.迪杰斯特拉最小堆
#include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<algorithm> using namespace std; const long long INF=9999999999999; const int maxn=2e5+10; struct X{ int id; long long time,cost; bool operator < (const X &a) const { if(time==a.time) return cost>a.cost; return time>a.time; } X(int f,long long g,long long h) { id=f,time=g,cost=h; } }; struct Edge { int from,to; long long time,cost; int next; }s[maxn]; int head[maxn]; bool flag[maxn]; long long ans1,ans2; long long dis[maxn]; int main() { int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(head,-1,sizeof head); memset(flag,0,sizeof flag); ans1=ans2=0; for(int i=0;i<=n;i++) dis[i]=INF; int cnt=0; for(int i=1;i<=m;i++) { int u,v; long long time,cost; scanf("%d%d%lld%lld",&u,&v,&time,&cost); s[cnt].from=u,s[cnt].to=v,s[cnt].time=time,s[cnt].cost=cost; s[cnt].next=head[u],head[u]=cnt++; s[cnt].from=v,s[cnt].to=u,s[cnt].time=time,s[cnt].cost=cost; s[cnt].next=head[v],head[v]=cnt++; } priority_queue<X>q; q.push(X(0,0,0)); dis[0]=0; while(!q.empty()) { X h=q.top(); q.pop(); if(flag[h.id]==1) continue; flag[h.id]=1; ans1=ans1+h.time; ans2=ans2+h.cost; for(int i=head[h.id];i!=-1;i=s[i].next) { if(flag[s[i].to]==0&&dis[s[i].to]>=dis[h.id]+s[i].time) { dis[s[i].to]=dis[h.id]+s[i].time; q.push(X(s[i].to,dis[h.id]+s[i].time,s[i].cost)); } } } printf("%lld %lld ",ans1,ans2); } return 0; }
2.先处理出哪些边是最短路上的，这样就构成了一个新的有向无环图，注意是无环。
每一个点最后肯定是连通的，那么我们只需要选择连到这个点的费用最小的边即可。
#include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> using namespace std; int T,n,m; long long INF=9999999999999999; const int maxn=100000+10; struct Edge { int from,to,next; long long t,c; }e[2*maxn]; int tot,head[maxn]; long long dis[maxn],cost[maxn]; bool flag[maxn]; void add(int a,int b,int t,int c) { e[tot].from=a, e[tot].to=b; e[tot].t=t, e[tot].c=c; e[tot].next=head[a]; head[a]=tot++; } void SPFA() { for(int i=1;i<=n;i++) dis[i]=INF; memset(flag,0,sizeof flag); queue<int>Q; dis[0]=0; Q.push(0); flag[0]=1; while(!Q.empty()) { int h=Q.front(); Q.pop(); flag[h]=0; for(int i=head[h];i!=-1;i=e[i].next) { if(dis[h]+e[i].t<dis[e[i].to]) { dis[e[i].to]=dis[h]+e[i].t; if(flag[e[i].to]==0) { flag[e[i].to]=1; Q.push(e[i].to); } } } } } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(head,-1,sizeof head); tot=0; for(int i=1;i<=m;i++) { int u,v;long long t,c; scanf("%d%d%lld%lld",&u,&v,&t,&c); add(u,v,t,c); add(v,u,t,c); } SPFA(); long long ans1=0,ans2=0; for(int i=1;i<n;i++) ans1=ans1+dis[i]; for(int i=1;i<=n;i++) cost[i]=INF; for(int i=0;i<tot;i++) if(dis[e[i].from]+e[i].t==dis[e[i].to]) cost[e[i].to]=min(cost[e[i].to],e[i].c); for(int i=1;i<n;i++) ans2=ans2+cost[i]; printf("%lld %lld ",ans1,ans2); } return 0; }