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

CodeForces - 545E Paths and Trees 最短路建树

题目链接:点击查看

Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows.

Let's assume that we are given a connected weighted undirected graph G = (V, E) (here V is the set of vertices, E is the set of edges). The shortest-path tree from vertex u is such graph G1 = (V, E1) that is a tree with the set of edges E1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to G1 are the same.

You are given a connected weighted undirected graph G and vertex u. Your task is to find the shortest-path tree of the given graph from vertex u, the total weight of whose edges is minimum possible.

Input

The first line contains two numbers, n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of vertices and edges of the graph, respectively.

Next m lines contain three integers each, representing an edge — ui, vi, wi — the numbers of vertices connected by an edge and the weight of the edge (ui ≠ vi, 1 ≤ wi ≤ 109). It is guaranteed that graph is connected and that there is no more than one edge between any pair of vertices.

The last line of the input contains integer u (1 ≤ u ≤ n) — the number of the start vertex.

Output

In the first line print the minimum total weight of the edges of the tree.

In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from 1 in the order they follow in the input. You may print the numbers of the edges in any order.

If there are multiple answers, print any of them.

Examples

Input

3 3
1 2 1
2 3 1
1 3 2
3

Output

2
1 2 

Input

4 4
1 2 1
2 3 1
3 4 1
4 1 2
4

Output

4
2 3 4 

题意:一个连通无向图,求包含u的一棵树,满足树上任意一点到u的最短距离等于原图中到那个点的最短距离。如果有多种这样的树,找到总权值最小的树。

题解:我们直接跑最短路就可以了,关键的地方在于当 dis[to]==dis[now.to]+e[i].d&&e[i].d<predis[to] ,predis[to]数组表示更新to这个点的那条边,当两种情况到达to的距离一样时,更新to的那条边越小,总的权值越小

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
struct edge{int to,nex,d,id;
}e[N*2];
int head[N],vis[N],pre[N],len;
int n,m,u;
ll dis[N],predis[N];
struct node{int to;node(){}node(int to_){to=to_;}bool operator <(const node &x)const{return dis[to]>dis[x.to];}
};void add(int x,int y,int z,int id)
{e[len].d=z;e[len].id=id;e[len].to=y;e[len].nex=head[x];head[x]=len++;
}
void DIJ()
{for(int i=1;i<=n;i++) predis[i]=dis[i]=1e18;priority_queue<node> q;node tmp,now;q.push(node(u));vis[u]=1;dis[u]=0;predis[u]=0;while(!q.empty()){now=q.top();q.pop();vis[now.to]=0;for(int i=head[now.to];i!=-1;i=e[i].nex){int to=e[i].to;//	cout<<to<<endl;if(dis[to]>dis[now.to]+e[i].d || dis[to]==dis[now.to]+e[i].d&&e[i].d<predis[to]){dis[to]=dis[now.to]+e[i].d;pre[to]=e[i].id;predis[to]=e[i].d;if(!vis[to]){q.push(node(to));vis[to]=1;}}}}
}
int main()
{int x,y,z;memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z,i);add(y,x,z,i);}scanf("%d",&u);DIJ();ll ans=0;for(int i=1;i<=n;i++) ans+=predis[i];cout<<ans<<endl;ans=0;for(int i=1;i<=n;i++){if(i==u) continue;++ans;printf("%d%c",pre[i]," \n"[ans==n-1]);}return 0;
}

 

相关文章:

ADB学习笔记

简介&#xff1a; ADB的全称为Android Debug Bridge&#xff08;调试桥&#xff09;&#xff0c; 它是一个客户端-服务器端程序&#xff0c;其中客户端是你用来操作的电脑, 服务器端是android设备。作用显而易见&#xff0c;能方便我们在PC上对手机进行调试的一些工作。 原理…...

http load介绍

前几天工作中要对项目的接口做简单压测&#xff0c;就使用了http load做了简单测试&#xff0c;下面介绍一下这款工具的使用说明。简介&#xff1a;http_load是基于linux平台的性能测试工具&#xff0c;它体积非常小&#xff0c;仅100KB。它以并行复用的方式运行&#xff0c;可…...

TestNG使用总结

TestNG简介&#xff1a; TestNG是一个测试框架&#xff0c;其灵感来自JUnit和NUnit&#xff0c;但同时引入了一些新的功能&#xff0c;使其功能更强大&#xff0c;使用更方便。 TestNG相较于Junit的优点&#xff1a; 可指定执行顺序&#xff0c; dependsOnMethods 属性来应对…...

面向对象编程的弊端

英文原文&#xff1a;What’s Wrong with OOP and FP 我不理解为什么人们会对面向对象编程和函数式编程做无休无止的争论。就好象这类问题已经超越了人类智力极限&#xff0c;所以你可以几个世纪的这样讨论下去。经过这些年对编程语言的研究&#xff0c;我已经清楚的看到了问题…...

flex 计算指定日期是本年度第几周

/** * 计算指定日期是本年度第几周 *传日年月日&#xff0c;返回number */ private function weekOfYear(yyyy:Number,mm:Number,dd:Number):Number{ var myDate:Date new Date(yyyy, mm - 1, dd); var startDate:Date new Date(yyyy,0,1); v…...

webservice学习记录笔记(一)

一、先理解什么是服务 现在的应用程序变得越来越复杂&#xff0c;甚至只靠单一的应用程序无法完成全部的工作。更别说只使用一种语言了。 写应用程序查询数据库时&#xff0c;并没有考虑过为什么可以将查询结果返回给上层的应用程序&#xff0c;甚至认为&#xff0c;这就是数…...

接口测试那些事儿

什么是接口&#xff1f; 首先&#xff0c;在讲接口测试之前&#xff0c;我们先要搞清楚接口类型的概念。 接口&#xff1a;可能是系统与系统&#xff08;包括服务与服务&#xff09;之间的调用&#xff0c;像A系统&#xff08;服务&#xff09;给B系统&#xff08;服务&#x…...

Jmeter访问HTTPS请求

公司最近在搞全站HTTPS改造&#xff0c;进一步提高网站的安全性&#xff0c;防止运营商劫持。那么&#xff0c;改造完成后&#xff0c;所有前后端的URL将全部为https。 So &#xff0c;研究下怎么用Jmeter访问https请求呢。 其实很简单&#xff0c; 第一步在jmeter中创建HTT…...

JSON相关知识点

JSON是工作中经常会遇到的一种数据结构&#xff0c;下面来讲讲与他相关的一些知识点。 JSON简介&#xff1a; JSON: JavaScript Object Notation(JavaScript 对象表示法) JSON 是存储和交换文本信息的语法,类似 XML。 JSON 比 XML 更小、更快&#xff0c;更易解析。 JSONObj…...

mysql重置Root密码

方法一: 在my.ini的[mysqld]字段加入&#xff1a; skip-grant-tables 重启mysql服务&#xff0c;这时的mysql不需要密码即可登录数据库 然后进入mysql mysql>use mysql; mysql>更新 user set passwordpassword(新密码) WHERE Userroot; mysql>flush privileges; 运…...

idea常用技巧收集

idea相比eclipse的优点我在这里就不赘述了&#xff0c;更多参考&#xff1a;idea官网,本文重点讲下自己在idea使用过程中常用的一些技巧&#xff0c;以后随时更新…… 主要分成三大块&#xff1a; 1. 系统设置 2. 快捷键 3. 其他设置 系统设置 主题风格设置&#xff1a;默…...

初识spring RestTemplate

《spring实战》读书笔记之初识spring RestTemplate。首先需要先了解下什么是REST。 REST&#xff1a;官方解释&#xff0c;表述性状态转移。 感觉还是不知所云&#xff0c;参考下怎样用通俗的语言解释REST&#xff0c;以及RESTful&#xff1f; 即URL定位资源&#xff0c;用H…...

ZOJ - 2968 Difference Game 思维

题目链接&#xff1a;点击查看 Now you are going to play an interesting game. In this game, you are given two groups of distinct integers and C coins. The two groups, named Ga and Gbrespectively, are not empty and contain the same number of integers at firs…...

单元测试框架-Junit介绍

在工作中编写接口脚本中经常用到junit作为测试框架&#xff0c;下面总结一下junit的用法和编写规范&#xff0c;供大家参考。 junit简介&#xff1a; 基于Java语言的单元测试框架&#xff0c;在日常工作中被广泛运用于单元测试和接口测试。 junit官网&#xff1a;http://jun…...

javaSE之动态代理

动态代理技术&#xff1a; 使程序更加灵活&#xff0c;可以在代理java类的时候加入一些功能。 很类似过滤器&#xff0c;区别&#xff1a; 过滤器是自己编写西横须实现的功能 动态代理是JVM内部机制 实现步骤&#xff1a; 1.真是业务对象&#xff08;被代理对象&#xff09; 2…...

Hibernate 主键生成策略

<generator>:主键生成策略 increment:递增,hibernate自动产生主键.max(id) ,采用带走1算法,多进程/集群环境下不推荐使用. identity:设置表主键是自增字段,映射文件采用该策略,依赖底层库, auto_increment identity 适用于MySQL、DB2、MS SQL Server&#xff0c;…...

flex 事件机制详解

事件机制的工作流程 1&#xff1a;关于事件流 当一个事件发生&#xff0c;必然存在一个派发事件的对象&#xff0c;这里称之为目标对象。 当事件发生后flashPlayer生成一个携带数据的对象&#xff0c;然后检查目标对象是否处于显示层中&#xff0c;如果是则遍历从根容器一直到目…...

CodeForces - 557C Arthur and Table 预处理 前缀

题目链接&#xff1a;点击查看 题意&#xff1a;有n个桌腿&#xff0c;要砍掉某些桌腿&#xff0c;使剩下的桌腿中长度最大的桌腿的数量如果超过一半。砍掉每个桌腿需要付出代价。求最小的代价和&#xff0c;操蛋&#xff0c;砍掉的意思是直接去掉&#xff0c;我理解成了&…...

MD5加密算法详解

注&#xff1a;MD5不是绝对的安全&#xff0c;有俩md5解决 /******************************************************************************* * keyBean 类实现了RSA Data Security, Inc.在提交给IETF 的RFC1321中的keyBean message-digest * 算法。 *****************…...

每天一个adb命令:screen 命令详解

screen命令分为截屏screencap命令及录制视频screenrecord命令。 screencap命令&#xff1a; sage: screencap [-hp] [-d display-id] [FILENAME]-h: this message-p: save the file as a png.-d: specify the display id to capture, default 0. If FILENAME ends with .png …...

markdown编写入门

什么是markdown&#xff1f; Markdown 是一种轻量级的「标记语言」&#xff0c;通过简单的标记符号来格式化排版&#xff0c;是文本展现的更加优美&#xff0c;形象。 markdown优点&#xff1a; 1.不像office&#xff0c;存在版本兼容问题&#xff0c;markdown无此问题&#…...

《Maven实战》读书笔记

之前对Maven有些认识&#xff0c;通过这本书《Maven实战》一起系统的回顾一下&#xff0c;总结的东西不会很全面&#xff0c;但都是日常工作中最常用的。 简介&#xff1a; maven翻译为“知识的积累”&#xff0c;基于项目对象模型&#xff08;Project Object Model&#xff0…...

记一次爬虫实践(一):思路及模拟登录

需求背景 因为我们的应用通常运行在h5上&#xff0c;因此图片格式选择了加载较快的webp格式&#xff0c;但是运营提起有在pc上批量下载图片&#xff08;要求图片格式&#xff09;的需求&#xff0c;目前比较麻烦&#xff0c;需要登录h5-找到接口中对应图片资源-一张张另存为到…...

SSH免密码登录

公司服务器很多的话&#xff0c;如果每次连接都需要输入密码&#xff0c;那就太麻烦了。So&#xff0c;免密登录就可以大大提高我们的工作效率了。 下面介绍ssh免密登录的方法&#xff1a; 实现步骤&#xff1a; 1.在你的自己的机器下面使用ssh-keygen命令来实现创建公钥 使…...

log4j学习demo

log4j简介 Log4j是Apache的一个开放源代码项目&#xff0c;是项目中比较常用的日志记录组件。 引入log4j <dependency><groupId>log4j</groupId><artifactId>log4j</artifactId><version>1.2.14</version></dependency> log4…...

flex验证座机,手机的框架

import mx.utils.StringUtil; import mx.validators.ValidationResult; import mx.validators.Validator; public class PhoneValidator extends Validator { public function PhoneValidator() { super(); } private var _phoneInvalid:String"正确格式(010-865…...

CodeForces - 555C Case of Chocolate set pair

题目链接&#xff1a;点击查看 题意&#xff1a;有一个n*n的矩形&#xff0c;给你对角线上的坐标&#xff0c;给你一个方向&#xff0c;问能走几个坐标&#xff0c;遇到之前已经经过的坐标就停止 题解&#xff1a;当给你一个坐标(x,y)&#xff0c;方向向上时&#xff0c;他能…...

HDU - 2328 Corporate Identity / POJ - 3080 Blue Jeans kmp 枚举

题目连接&#xff1a;点击查看 题意&#xff1a;n个字符串最长公共子串&#xff0c;相同长度就找字典序小的&#xff0c;poj那个是长度小于3&#xff0c;输出那句话 题解&#xff1a;以某一字符串为基准&#xff0c;枚举每个子串&#xff0c;然后暴力kmp即可&#xff0c;特记…...

spring装配bean

最近在看《spring实战》一书&#xff0c;记录下spring装配bean这一章中自己学到的一些知识点。下面简单说明下bean和装配这两个概念的意思。 bean&#xff1a;在spring中代表组件&#xff0c;通过bean将不同的组件联系在一起。装配&#xff1a;是指创建应用对象之间协作关系的行…...

POJ - 1451 T9 字典树

题目连接&#xff1a;点击查看 Background A while ago it was quite cumbersome to create a message for the Short Message Service (SMS) on a mobile phone. This was because you only have nine keys and the alphabet has more than nine letters, so most character…...

每天一个adb命令:am 命令详解

am 这个命令可以帮助我们直接启动activity、service及广播。 adb shell am 可以查看命令的详细说明。 usage: am [subcommand] [options] usage: am start [-D] [-W] [-P <FILE>] [--start-profiler <FILE>][--sampling INTERVAL] [-R COUNT] [-S] [--opengl-tra…...

常用HTML标签简介

HTML&#xff1a;超文本标记语言 这个没啥技术含量&#xff0c;这里只是简单介绍&#xff0c;主要是要熟能生巧。 布局相关&#xff1a; <!-- 标记导航 --><nav></nav> <!-- 标记侧边栏 --><aside></aside> <!-- 标记正文 --><…...

Appium学习遇到的坑

安装篇 Q1&#xff1a;安装时要求java运行环境为最低1.8&#xff0c;我原先的jdk1.7无法运行。 A1&#xff1a;升级jdk后解决。附appium安装教程 配置篇 Q2&#xff1a;运行提示error&#xff1a;Error: Android bootstrap socket crashed: Error: getaddrinfo ENOTFOUND lo…...

Python高级特性

Python高级特性 切片迭代及迭代器列表生成式生成器 这些高级特性的作用都是一样的&#xff0c;为了代码的简洁、高效运行。 切片 切片让取一个list或tuple的部分元素变得相当简单&#xff0c; e.g: L[‘jack’,’mike’,’jerry’] 那么第一个位置&#xff0c;索引为0&a…...

《移动App测试实战》读书笔记

总的来讲&#xff0c;这本书基本涵盖了移动App测试的方方面面&#xff0c;并结合各个专题做了简单讲解&#xff0c;对于扩展无线端测试的知识面有极大的好处&#xff0c;缺点是知识点点到为止&#xff0c;毕竟全书300多页的篇幅也不可能对知识点进行专题讲解。书中作者提到的一…...

CodeForces - 555A Case of Matryoshkas

题目链接&#xff1a;点击查看 题意&#xff1a;太他妈难懂了&#xff0c;大致意思就是有k条链&#xff0c;想得到1->2->..>n&#xff0c;这样的链&#xff0c;有两种操作&#xff0c;一种是断开链&#xff0c;需要1秒&#xff0c;一种是可以将1个单独的数字接在链后…...

Appium简介

Appium简介 Appium is an open source, cross-platform test automation tool for native, hybrid and mobile web apps, tested on simulators (iOS), emulators (Android), and real devices (iOS, Android, Windows). 优缺点 优点显而易见&#xff0c;支持webview、hybri…...

shell编写图片抓取器

最近在看《Linux Shell脚本攻略》一书&#xff0c;书中有个图片抓取器的script&#xff0c;抓取出来记录一下。适用范围&#xff1a;适合抓取html里符合img标签正则规则的图片。 #!/bin/bash if [ $# -ne 3 ] thenecho "Usage: $0 URL -d DIRECTORY"exit -1 fi for …...

每天一个adb命令:pm 命令详解

介绍adb shell中一个很重要的命令——pm&#xff08;Package Manager&#xff09;&#xff0c;这个命令主要用于获取和安装在 Android 设备上的应用信息。 关于pm命令的用法解析。命令行下输入adb shell pm即可获得关于pm的用法帮助&#xff0c;如下所示&#xff1a; usage: …...

工具介绍:ITerm 2

今天介绍一款终端工具ITerm2&#xff0c;有了它&#xff0c;大大提供了我们的工作效率&#xff1b;官方地址&#xff1a;http://www.iterm2.com/ 颜控首选&#xff0c;不多说&#xff0c;上图&#xff1a; bg图片、字体、颜色等都可以在Preferences里设置&#xff0c;强大&…...

LRU算法

#include <iostream> #include <list> #include <map> using namespace std; class LRU {struct node {int key, val;node(int k_ 0, int v_ 0) {key k_;val v_;}};public:int cap; // 大小map<int, list<node>::iterator> mp;list<node&…...

八大设计模式原则

1.依赖倒置原则 高层模块不依赖底层模块&#xff0c;二者都应该依赖抽象 抽象不依赖实现细节&#xff0c;实现细节应该依赖于抽象 这一原则与下面的针对接口编程而不是针对实现编程是一个道理&#xff0c;我们设计一个程序&#xff0c;我们应该先想好我们想要抽象什么&#x…...

到底什么是互联网思维

本文转字http://www.managershare.com/2014/04/28/internet-thinking-magic-power/课前秀&#xff1a;三个段子 第一个段子&#xff1a;有一个毫无餐饮行业经验的人&#xff0c;他开了一家餐馆&#xff0c;菜品只有12道&#xff0c;在北京只有两家分店&#xff1b;仅两个月时间…...

flex勾选,自动刷新

mxml: <s:CheckBox label"刷新" buttonMode"true" id "frc" selected "{model.autoFresh}" change "{model.startAutoQuery(frc.selected)}"/> <s:Label text"间隔"/> &…...

javaSE之类加载器

类加载器&#xff0c;说白了就是加载类的呵呵 .类加载器负责将.class文件&#xff08;可能在磁盘上&#xff0c;也可能在网络上&#xff09;加载到内存中&#xff0c;并为之生成对应的java.lang.Class对象 .当JVM启动时&#xff0c;会形成由三个类加载器组成的初始类加载器层次…...

基于数据驱动的接口自动化测试解决方案

总结一下我么项目中使用的基于数据驱动的接口自动化测试解决方案&#xff0c;仅供大家参考。1.接口框架设计结构 2.接口测试脚本设计原则 3.持续集成 这块用jenkins就可以了&#xff0c;就不介绍了&#xff0c;目前我们项目的集成规则介绍一下&#xff1a; 1.脚本job与应用对…...

每天一个adb命令:wm命令详解

wm命令可以用于获取屏幕分辨率、像素密度等。 前提&#xff1a;Android4.3及以上 usage: wm [subcommand] [options]wm size [reset|WxH]wm density [reset|DENSITY]wm overscan [reset|LEFT,TOP,RIGHT,BOTTOM]wm size: return or override display size.wm density: overrid…...

每天一个adb命令:dumpsys命令详解

dumpsys是一个能帮助我们对手机进行性能分析的命令&#xff0c;它可以帮助我们获取电池、内存、cpu、磁盘、wifi等等信息&#xff0c;具体能查询的信息可以通过命令&#xff1a; adb shell dumpsys | grep DUMP OF SERVICE DUMP OF SERVICE DockObserver: DUMP OF SERVICE Sm…...

互联网产品与需求三 需求优先级定义

需求优先级定义即便是已经少选评估出来的需求&#xff0c;很多时候量也是非常大的&#xff0c;而哪些该做&#xff0c;哪些不该做&#xff0c;很多时候我们会遇到&#xff1a;Boss拍脑袋要这么做自己拍脑袋要这么做顾此失彼&#xff0c;左顾右盼其实&#xff0c;在产品不同阶段…...

flex dataGrid组件全选,反选,并获取选中值,代码详解

//1 组建重写 package hxht.comps.datagrid{ import flash.display.DisplayObject; import flash.events.Event; import flash.events.MouseEvent; import mx.collections.ArrayCollection; import mx.collections.IList; import mx.events.DynamicEvent; import spark.comp…...