最短路和最小生成树（dijkstra和prim)（prim模板）

题目：P3366 【模板】最小生成树
题目： P4779 【模板】单源最短路径（标准版）

最小生成树：
    边权之和最小
    每次加入（染）最短的边
    优先队列放的是边长（即边权）（以该点为终点的边的边长）
最短路：
    从原点到任意一点的距离最小
    每次加入（染）离原点最短的边
    优先队列放的是原点到该点的距离

以下是最小生成树（prim)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=5e3+7;
int const M=2e5+7;
int cnt,ans;
int head[N];
struct node{
int a,next,len;
}e[M<<1];
void add(int x,int y,int len){ //x为起点，y为终点，此函数表示从x到y有一条权值为len的有向边
e[++cnt].a =y;
e[cnt].len =len;
e[cnt].next =head[x];
head[x]=cnt;
}
struct L{
int a,dis;
friend bool operator<(L a,L b){
return a.dis > b.dis ;
}
};

int vis[N],dis[N];//dis表示终点是e[i].a的边权（边长） 
void prim(int s){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    priority_queue<L>pq;
    pq.push( (L){s,0} );
    dis[s]=0;
    while(!pq.empty()){
        int u=pq.top().a,w=pq.top().dis;pq.pop();
        if(vis[u]) continue;
        ans+=w;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next){
            if(vis[e[i].a]) continue;
            if( e[i].len < dis[e[i].a] ){   //与dijkstra不一样的地方 ,此处dis表示以e[i].a为终点的权值（边长） 
                dis[e[i].a]=e[i].len ;      //与dijkstra不一样的地方
                pq.push( (L){e[i].a,dis[e[i].a]} );
            }
        }
    }    
}

int n,m;
int main(){
cin >> n >> m;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;++i){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);add(b,a,c);
}
prim(1);
if(ans) cout << ans ;
else cout << "orz";
return 0;
}

以下是最短路（dijkstra)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int const M=1e5+7;
int cnt;
int head[N];
struct node{
int a,next,len;
}e[M<<1];
void add(int x,int y,int len){
e[++cnt].a =y;
e[cnt].len =len;
e[cnt].next =head[x];
head[x]=cnt;
}
struct L{
int a,dis;
friend bool operator<(L a,L b){
return a.dis > b.dis ;
}
};

int vis[N],dis[N];
void dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<L>pq;
    pq.push((L){s,0});
    dis[s]=0;
    while(!pq.empty()){
        int u=pq.top().a;pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next){
            if(vis[e[i].a]) continue;
            if(dis[u]+e[i].len < dis[e[i].a]){
                dis[e[i].a]=dis[u]+e[i].len ;
                pq.push( (L){e[i].a ,dis[e[i].a]} );
            }
        }
    }    
}

int n,m,s;
int main(){
memset(head,-1,sizeof(head));
cin >> n >> m >> s;
for(int i=1;i<=m;++i){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c); //*表示从a到b有一条权值为c的有向边 *
}
dijkstra(s);
for(int i=1;i<=n;++i){
cout << dis[i] << " ";
}
return 0;
}