[题意]
给定一个无向图, 求这个图满足所有点到顶点的最短路径不变的最小生成树
[AC]
注意双向边要开 2*maxm
注意优先级队列
- #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;
- }
来源: http://www.bubuko.com/infodetail-2646233.html