当前位置：首页 > news >正文

545E. Paths and Trees

news 来源：原创 2024/5/19 16:51:06

题目链接

题意：给定一个无向图和一个点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:])