[Codeforces 545E] Paths and Trees

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

[题目链接]

https://codeforces.com/contest/545/problem/E

[算法]

首先求 u 到所有结点的最短路

记录每个节点最短路径上的最后一条边

答案即为以u为根的一棵最短路径生成树

时间复杂度 : O(NlogN)

[代码]

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + ;

const long long INF = 1e60;

struct edge

{

        int to , w , nxt;

} e[MAXN << ];

int n , m , s , tot;

int head[MAXN],u[MAXN],v[MAXN],w[MAXN],last[MAXN];

long long dist[MAXN];

bool visited[MAXN],vis[MAXN << ];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline void addedge(int u,int v,int w)

{

        tot++;

        e[tot] = (edge){v,w,head[u]};

        head[u] = tot;

}

inline void dijkstra(int s)

{

        priority_queue< pair<long long,int> , vector< pair<long long,int> > ,greater< pair<long long,int> > > q;

        for (int i = ; i <= n; i++)

        {

                dist[i] = INF;

                visited[i] = false;

        }

        dist[s] = ;

        q.push(make_pair(,s));

        while (!q.empty())

        {

                int cur = q.top().second;

                q.pop();

                if (visited[cur]) continue;

                visited[cur] = true;

                for (int i = head[cur]; i; i = e[i].nxt)

                {

                        int v = e[i].to , w = e[i].w;

                        if (!visited[v] && dist[cur] + w <= dist[v])

                        {

                                if (dist[cur] + w < dist[v]) last[v] = i;

                                else if (w < e[last[v]].w) last[v] = i;

                                dist[v] = dist[cur] + w;

                                q.push(make_pair(dist[v],v));

                        }

                }

        }

}

int main()

{

        read(n); read(m);

        for (int i = ; i <= m; i++)

        {

                read(u[i]); read(v[i]); read(w[i]);

                addedge(u[i],v[i],w[i]);

                addedge(v[i],u[i],w[i]);

        }

        read(s);

        dijkstra(s);

        for (int i = ; i <= n; i++) vis[last[i]] = true;

        vector< int > ans;

        long long res = ;

        for (int i = ; i <= tot; i += )

        {

                if (vis[i] || vis[i - ])

                {

                        ans.push_back(i >> );

                        res += e[i].w;

                }

        }

        printf("%I64d\n",res);

        for (unsigned i = ; i < ans.size(); i++)

                if (i == ) printf("%d",ans[i]);

                else printf(" %d",ans[i]);

        printf("\n");

        return ;

}