先上一波题目qwq https://www.luogu.org/problem/P1629·
复习了一波 dijstra 的 priority_queue（优先队列）优化的写法
tips： 求单项路中求每个点走到固定点的最短路可以把每条路倒过来 然后从固定点开始跑一次最短路即可
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int M=10007,mx=2e7; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } struct qwq{ int id,d; bool operator<(const qwq&x)const{return x.d<d;} }; priority_queue<qwq>q; int cnt,first[M]; struct node{int to,next,w;}e[100007],e1[100007]; void ins(int a,int b,int w){ cnt++; e[cnt].to=b; e[cnt].w=w; e[cnt].next=first[a]; first[a]=cnt; } int cnt1,first1[M]; void ins1(int a,int b,int w){ cnt1++; e1[cnt1].to=b; e1[cnt1].w=w; e1[cnt1].next=first1[a]; first1[a]=cnt1; } int n,m,dis[M],dis1[M]; void dj1(){ q.push((qwq){1,0}); dis[1]=0; while(!q.empty()){ qwq x=q.top(); q.pop(); if(x.d>dis[x.id]) continue; for(int i=first[x.id];i;i=e[i].next){ int now=e[i].to; if(dis[now]>dis[x.id]+e[i].w){ dis[now]=dis[x.id]+e[i].w; q.push((qwq){now,dis[now]}); } } } } void dj2(){ q.push((qwq){1,0}); dis1[1]=0; while(!q.empty()){ qwq x=q.top(); q.pop(); if(x.d>dis1[x.id]) continue; for(int i=first1[x.id];i;i=e1[i].next){ int now=e1[i].to; if(dis1[now]>dis1[x.id]+e1[i].w){ dis1[now]=dis1[x.id]+e1[i].w; q.push((qwq){now,dis1[now]}); } } } } int main(){ int x,y,w,ans=0; n=read(); m=read(); for(int i=1;i<=n;i++) dis[i]=mx,dis1[i]=mx; for(int i=1;i<=m;i++) x=read(),y=read(),w=read(),ins(x,y,w),ins1(y,x,w); dj1(); dj2(); for(int i=2;i<=n;i++) ans+=dis[i]+dis1[i]; printf("%d\n",ans); return 0; }