城市平乱
时间限制:1000 ms | 内存限制:65535 KB
难度:4
南将军统领着N个部队,这N个部队分别驻扎在N个不同的城市。
他在用这N个部队维护着M个城市的治安,这M个城市分别编号从1到M。
现在,小工军师告诉南将军,第K号城市发生了暴.乱,南将军从各个部队都派遣了一个分队沿最近路去往暴.乱城市平乱。
现在已知在任意两个城市之间的路行军所需的时间,你作为南将军麾下最厉害的程序员,请你编写一个程序来告诉南将军第一个分队到达叛乱城市所需的时间。
注意,两个城市之间可能不只一条路。
每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数,M表示城市数,P表示城市之间的路的条数,Q表示发生暴.乱的城市编号。
随后的一行是N个整数,表示部队所在城市的编号。
再之后的P行,每行有三个正整数,a,b,t(1<=a,b<=M,1<=t<=100),表示a,b之间的路如果行军需要用时为t
数据保证暴.乱的城市是可达的。
1 3 8 9 8 1 2 3 1 2 1 2 3 2 1 4 2 2 5 3 3 6 2 4 7 1 5 7 3 5 8 2 6 8 2
4
思路:
Dijkstra + 最短路即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <utility> #include <queue> using namespace std; typedef pair<int, int> pii; const int VMAX = 1005; const int EMAX = 100005 * 2; const int INF = 999999999; int v[EMAX], fir[VMAX], next[EMAX], w[EMAX]; int ind, m; int army[VMAX]; int d[VMAX], vis[VMAX]; void add_edge (int f, int t, int val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ++ind; } void Dij (int x) { for (int i = 1; i <= m; ++i) { d[i] = i == x ? 0 : INF; vis[i] = 0; } priority_queue<pii, vector<pii>, greater<pii> > q; q.push(make_pair(d[x], x)); while (!q.empty()) { pii k = q.top(); q.pop(); int y = k.second; if (vis[y]) continue; vis[y] = 1; for (int e = fir[y]; e != -1; e = next[e]) { int yy = v[e]; if (d[yy] > d[y] + w[e]) { d[yy] = d[y] + w[e]; q.push(make_pair(d[yy], yy)); } } } } int main() { int t; scanf("%d", &t); while (t--) { ind = 0; memset(fir, -1, sizeof(fir)); int n, p, q; scanf("%d%d%d%d", &n, &m, &p, &q); for (int i = 0; i < n; ++i) { scanf("%d", &army[i]); } while (p--) { int a, b, val; scanf("%d%d%d", &a, &b, &val); add_edge(a, b, val); add_edge(b, a, val); } int Min = INF; for (int i = 0; i < n; ++i) { Dij(army[i]); Min = min(Min, d[q]); } printf("%d\n", Min); } return 0; }
相关推荐
笔记本屏幕关闭,就是关闭屏幕你需要我平乱什么
5G通信行业、网络优化、通信工程建设资料。
29-【智慧城市与政府治理分会场】10亿大数据助推都市治理-30页.pdf
ABB IRC5 Compact 机器人产品手册
5G通信行业、网络优化、通信工程建设资料
5G通信行业、网络优化、通信工程建设资料。
5G通信、网络优化与通信建设
网络技术和计算机技术发展至今,已经拥有了深厚的理论基础,并在现实中进行了充分运用,尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代,所以对于信息的宣传和管理就很关键。系统化是必要的,设计网上系统不仅会节约人力和管理成本,还会安全保存庞大的数据量,对于信息的维护和检索也不需要花费很多时间,非常的便利。 网上系统是在MySQL中建立数据表保存信息,运用SpringBoot框架和Java语言编写。并按照软件设计开发流程进行设计实现。系统具备友好性且功能完善。 网上系统在让售信息规范化的同时,也能及时通过数据输入的有效性规则检测出错误数据,让数据的录入达到准确性的目的,进而提升数据的可靠性,让系统数据的错误率降至最低。 关键词:vue;MySQL;SpringBoot框架 【引流】 Java、Python、Node.js、Spring Boot、Django、Express、MySQL、PostgreSQL、MongoDB、React、Angular、Vue、Bootstrap、Material-UI、Redis、Docker、Kubernetes
5G通信行业、网络优化、通信工程建设资料
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Gif动画录制软件是一款方便好用的小软件,使用此工具,您可以记录屏幕的选定区域,网络摄像头的实时提要或草图板上的实时图形。之后,您可以编辑动画并将其另存为gif,apng,视频,psd或png图像。
协同供应链集成(Collaborative Supply Chain Integration,CSCD是数字化转型解决方案中的重要一环,旨在通过技术手段实现供应链各环节的无缝对接与高效协作。V70版本作为该解决方案的一个升级版,可能包含了更加先进的功能和工具,以支持企业在复杂的商业环境中保持竞争力。这个资料包“协同供应链集成详细功能介绍V70.rar”很可能提供了对V70版本功能的深入剖析,包括了如何利用最新的数字化工具和技术来优化库存管理、订单处理、物流跟踪、供应商管理以及客户关系管理等关键供应链过程。它可能详细介绍了实时数据共享、自动化流程、预测分析、风险管理和智能决策支持系统等创新功能,这些功能有助于减少供应链中断,提高透明度,降低运营成本,并增强整个供应链网络的响应能力。通过这个资料,企业可以获得实施协同供应链集成的全面指导,了解如何通过集成的信息系统和平台,实现数据的一致性和准确性,以及如何通过合作伙伴之间的紧密协作,提升整个供应链的效率和灵活性。这对于追求数字化转型的企业来说,是一个宝贵的资源,因为它不仅提供了理论框架,还可能包含了实际案例研究、最佳实践和实施策略,帮助企业
英飞凌官方ADS库1.9.20版
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
5G通信行业、网络优化、通信工程建设资料。
5G通信行业、网络优化、通信工程建设资料
5G通信行业、网络优化、通信工程建设资料
jump(1).mobileprovision
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。