【CCF】交通规划 Dijstra变形 优先级队列重载

#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<queue>using namespace std;int n,m;const int maxn=1e4+2;const int maxm=1e5+2;const int inf=0x3f3f3f3f;struct node{ ???int to; ???int nxt; ???int w;}e[2*maxm];int head[maxn];int tot;int dis[maxn];int fa[maxn];bool vis[maxn];void init(){ ???memset(head,-1,sizeof(head)); ???tot=0;}void add(int u,int v,int w){ ???e[tot].to=v; ???e[tot].w=w; ???e[tot].nxt=head[u]; ???head[u]=tot++;}struct Node{ ???int id; ???int fa; ???int d; ???Node(int _id,int _d,int _fa):id(_id),d(_d),fa(_fa){} ???bool operator < (const Node& a) const{ ???????if(d!=a.d){ ???????????return d>a.d; ???????} ???????return fa>a.fa; ???}};int dijkstra(int s){ ???priority_queue<Node> Q; ???memset(vis,false,sizeof(vis)); ???memset(dis,inf,sizeof(dis)); ???memset(fa,inf,sizeof(fa)); ???dis[s]=0; ???fa[s]=0; ???Q.push(Node(s,dis[s],fa[s])); ???int ans=0; ???while(!Q.empty()){ ???????Node q=Q.top(); ???????Q.pop(); ???????int u=q.id; ???????if(vis[u]) continue; ???????vis[u]=true; ???????ans+=q.fa; ???????for(int i=head[u];i!=-1;i=e[i].nxt){ ???????????int v=e[i].to; ???????????int w=e[i].w; ???????????if(dis[u]+w<dis[v]){ ???????????????dis[v]=dis[u]+w; ???????????????fa[v]=w; ???????????}else if(dis[u]+w==dis[v]&&w<fa[v]){ ???????????????fa[v]=w; ???????????} ???????????Q.push(Node(v,dis[v],fa[v])); ???????} ???} ???return ans; ???}int main(){ ???while(~scanf("%d%d",&n,&m)){ ???????if(n==1){ ???????????printf("0\n"); ???????????continue; ???????} ???????init(); ???????int u,v,w; ???????for(int i=0;i<m;i++){ ???????????scanf("%d%d%d",&u,&v,&w); ???????????add(u,v,w); ???????????add(v,u,w); ???????} ???????int ans=dijkstra(1); ???????printf("%d\n",ans); ???} ???????return 0;}