[CF 545E] Paths and Trees

作法：

首先把所有在最短路徑上的邊都找出來，並且定好方向（方向為到源點距離小的連到到源點距離大的），那麼可以知道其實最短路徑樹就是這些邊的一個有向生成樹，並且顯然一棵有向生成樹一定會是最短路徑樹（因為從原點到每個點經過的邊都是最好的邊）。而題目要求的是權值和最小的最短路徑樹，因此就等價於這張圖的最小有向生成樹（MDST）。回顧DMST的作法，第一步是先幫每個非源點的節點選擇權值最小的入邊，如果這些邊沒有形成環就結束了。而很幸運的因為這些都是最短路徑樹上的邊，所以顯然不會形成環，因此直接這樣取就會形成一棵樹了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF (1LL<<60)
using namespace std;
const int maxn=300000+10 ;
 
struct P{int x,y,dis ;};
vector<P> E ;
vector<int> v[maxn] ;
 
struct Q
{
    int id ; LL val ;
    bool operator < (const Q &rhs) const
    {
        return val>rhs.val ;
    }
};
 
priority_queue<Q> pq ;
LL d[maxn] ;
bool done[maxn] ;
int n ;
void Dijkstra(int st)
{
    for(int i=1;i<=n;i++) d[i]=INF ;
    d[st]=0 ; pq.push((Q){st,0}) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        if(done[u.id]) continue ;
        done[u.id]=1 ;
        for(auto i : v[u.id])
        {
            P &e=E[i] ;
            int to= e.x==u.id ? e.y : e.x ;
            if(d[to]>d[u.id]+e.dis)
                d[to]=d[u.id]+e.dis , pq.push((Q){to,d[to]}) ;
        }
    }
}
 
bool ok[maxn] ;
vector<int> ans ;
main()
{
    int m ; scanf("%d%d",&n,&m) ;
    for(int i=0;i<m;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        E.push_back((P){x,y,dis}) ;
        v[x].push_back(i) ;
        v[y].push_back(i) ;
    }
    int st ; scanf("%d",&st) ;
    Dijkstra(st) ;
 
    LL tot=0LL ;
    for(int i=1;i<=n;i++) if(i!=st)
    {
        LL mi=INF ;
        int id ;
        for(auto j : v[i])
        {
            P &e=E[j] ;
            int from=(e.x==i ? e.y : e.x) ;
            if(d[i]==d[from]+e.dis && e.dis<mi) mi=e.dis , id=j ;
        }
        ans.push_back(id) ;
        tot+=mi ;
    }
 
    printf("%I64d\n",tot) ;
    for(int i=0;i<n-1;i++) printf("%d%c",ans[i]+1,i+2==n?'\n':' ') ;
}