545E. Paths and Trees

题目链接

题意：给定一个无向图和一个点u，找出若干条边组成一个子图，要求这个子图中u到其他个点的最短距离与在原图中的相等，并且要求子图所有边的权重之和最小，求出最小值并输出子图的边号。

思路：先求一遍最短路，从所有到i点的满足最短路的边中选一条权最小的边。

Java程序

import java.io.PrintStream;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

import java.util.Scanner;

public class E545 {

    private static class Edge {

        int v;

        long w;

        int index;

        Edge(int v, long w, int index) {

            this.v = v;

            this.w = w;

            this.index = index;

        }

    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        PrintStream out = System.out;

        int n = in.nextInt(), m = in.nextInt();

        List<Edge>[] graph = new List[n];

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

            graph[i] = new ArrayList<E545.Edge>();

        }

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

            int v1 = in.nextInt() - 1;

            int v2 = in.nextInt() - 1;

            long w = in.nextLong();

            graph[v1].add(new Edge(v2, w, i));

            graph[v2].add(new Edge(v1, w, i));

        }

        int u = in.nextInt() - 1;

        Edge[] lastEdge = new Edge[n];

        final long[] min = new long[n];

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

            min[i] = -1;

        }

        min[u] = 0;

        Queue<Integer> q = new LinkedList<Integer>();

        q.add(u);

        while (!q.isEmpty()) {

            int v = q.poll();

            for (Edge edge : graph[v]) {

                int v1 = edge.v;

                long min1 = min[v] + edge.w;

                if ((min[v1] == -1) || (min1 < min[v1])

                        || (min1 == min[v1] && edge.w < lastEdge[v1].w)) {

                    min[v1] = min1;

                    lastEdge[v1] = edge;

                    q.add(v1);

                }

            }

        }

        long res = 0;

        boolean[] f = new boolean[m];

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

            if (lastEdge[i] != null) {

                res += lastEdge[i].w;

                f[lastEdge[i].index - 1] = true;

            }

        }

        out.println(res);

        StringBuilder s = new StringBuilder();

        boolean first = true;

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

            if (f[i]) {

                if (!first) {

                    s.append(" ");

                }

                s.append(i + 1);

                first = false;

            }

        }

        out.println(s.toString());

        in.close();

        out.close();

    }

}

 

Python代码

import heapq as hq

class edge(object):

    def __init__(self, to, w, nr):

        self.to = to

        self.w = w

        self.nr = nr

n, m = map(int, raw_input().split())

adj = [[] for _ in range(n + 1)]

for i in range(1, m+1):

    u, v, c = map(int, raw_input().split())

    adj[u].append((v, c, i))

    adj[v].append((u, c, i))

root = int(raw_input())

vis = [False] * (n+1)

q = [(0, 0, root, 0)]

ans = []

tot = 0

while q:

    d, c, n, e = hq.heappop(q)

    if vis[n]:

        continue

    ans.append(e)

    tot += c

    vis[n] = True

    for v, c, i in adj[n]:

        if not vis[v]:

            hq.heappush(q, (d+c, c, v, i))

ans = map(str, ans)

print tot

print " ".join(ans[1:])

 

上面的代码都是在codeforces上面抄过来的，自己写不出来。。。。