学校网站模板 红色/网站推广优化公司

题目链接

题意：给定一个无向图和一个点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 hqclass edge(object):def __init__(self, to, w, nr):self.to = toself.w = wself.nr = nrn, 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]:continueans.append(e)tot += cvis[n] = Truefor 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上面抄过来的，自己写不出来。。。。