题目链接

【题意】

给定一个n个结点m条边的无向图，并给出源点s，让你找出图中权值最小的最短路树，并输出这个权值

【思路】

对dijkstra算法稍作修改即可，在松弛操作的时候，在保留最短路的前提下，保正上一条边的权值是最小的，类似一种贪心的思想，最短路径确定的话，如果上一条边的权值最小，那么其余部分肯定会有更多的公共路径可以利用，最短路树的权值也就更小了。

#include
    
     using namespace std;typedef long long ll;typedef ll type;const ll inf=1e18;const int maxn=300050;struct Edge{    int from,to,id;    type dist;    Edge(int f,int t,type d,int i):from(f),to(t),dist(d),id(i){}};struct HeapNode{    type d;    int u;    HeapNode(type dd,int uu):d(dd),u(uu){}    bool operator<(const HeapNode& rhs)const{        return d>rhs.d;    }};struct Dijkstra{    int n,m;    vector
     
       edges;    vector
      
        g[maxn];    bool done[maxn];    type d[maxn];    int p[maxn];    void init(int n){        this->n=n;        for(int i=0;i
       
         que;        for(int i=0;i
        
         d[u]+e.dist){                    d[e.to]=d[u]+e.dist;                    p[e.to]=g[u][i];                    que.push(HeapNode(d[e.to],e.to));                }                else if(d[e.to]==d[u]+e.dist && e.dist