技术标签： 最短路径
https://www.luogu.org/problemnew/show/P1339
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。
FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。
给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。
#include<bits/stdc++.h>
using namespace std;
#define maxc 7000
#define maxt 3000
int t,c,ts,te;
struct Edge{
int next;
int to;
int w;
}e[2*maxc];
int head[maxt];
int ans=0;
void addEdge(int u,int v,int w){
int p=head[u];
while(p){
if(e[p].to==v&&e[p].w<=w) return ;
p=e[p].next;
}
e[++ans].to=v;
e[ans].w=w;
e[ans].next=head[u];
head[u]=ans;
}
int vis[maxt];
int dist[maxt];
void Dijkstra(){
priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;
for(int i=1;i<=t;i++) dist[i]=2000;
dist[ts]=0;
q.push(make_pair(0,ts));
while(!q.empty()){
int p=q.top().second;q.pop();
if(vis[p]) continue;
vis[p]=1;
int s=head[p];
while(s){
if(vis[e[s].to]==0&&dist[e[s].to]>dist[p]+e[s].w){
dist[e[s].to]=dist[p]+e[s].w;
q.push(make_pair(dist[e[s].to],e[s].to));
}
s=e[s].next;
}
}
}
int main(){
std::ios::sync_with_stdio(false);
cin>>t>>c>>ts>>te;
int u,v,w;
for(int i=0;i<c;i++){
cin>>u>>v>>w;
addEdge(u,v,w);
addEdge(v,u,w);
}
Dijkstra();
cout<<dist[te]<<endl;
return 0;
}
文章浏览阅读8k次，点赞2次，收藏6次。QT设置QLabel中字体的颜色其实，这是一个比较常见的问题。大致有几种做法：一是使用setPalette()方法；二是使用样式表；三是可以使用QStyle；四是可以在其中使用一些简单的HTML样式。下面就具体说一下，也算是个总结吧。第一种，使用setPalette()方法如下：QLabel *label = new QLabel(tr("Hello Qt!"));QP_qolable 字体颜色
文章浏览阅读3.7k次。使用C# 作为开发语言，将pb文件转换为cs文件的时候相信很多人都会遇到一个很棘手的问题，那就是protoc3环境下，import Timestamp的问题，在头部 import “google/protobuf/timestamp.proto”;的时候会抛异常：google/protobuf/timestamp.proto" was not found or had errors；解决办法【博主「pamxy」的原创文章的分享】：(注：之后才发现，不需要添加这个目录也可以，因为timestamp.p_import "google/protobuf/timestamp.proto" was not found or had errors.
文章浏览阅读4.1w次，点赞9次，收藏98次。一、准备工具: 1. app：VNET（抓包用）、京东； 安卓手机需要下载VNET软件。下载官网：https://www.vnet-tech.com/zh/ 2. 已安装部署好的青龙面板；二、抓包wskey: 1. 打开已下载的VNET软件，第一步先安装CA证书； 点击右下角三角形按钮（开始抓包按钮），会提示安装证书，点击确定即可，app就会将CA证书下载至手机里，随后在手机设置里进行安装，这里不同手机可能安装位置不同，具体..._jd_wsck
文章浏览阅读2.9k次，点赞7次，收藏3次。本文针对mybatis-plus自动填充第一次更新能正常填充，第二次更新无法自动填充问题。????mybatis-plus自动填充:当要填充的字段不为空时,填充无效问题的解决????先上一副官方的图：取自官方:https://mp.baomidou.com/guide/auto-fill-metainfo.html第三条注意事项为自动填充失效原因:MetaObjectHandler提供的默认方法的策略均为:如果属性有值则不覆盖,如果填充值为null则不填充以官方案例为例:```java_mybatisplus插入不放为空的字段
文章浏览阅读1w次，点赞25次，收藏94次。利用 Application Complier 完成MATLAB转exe文件_matlab exe
文章浏览阅读137次。近期项目需要研究paypal支付，官网上的指导写的过于复杂，可能是老外的思维和中国人不一样吧。难得是发现下面这篇文章：http://www.androidhive.info/2015/02/Android-integrating-paypal-using-PHP-MySQL-part-1/在这篇文章的基础上，查看SDK简化了代码，给出下面这个例子，..._paypal支付集成到anroid应用中
文章浏览阅读2.3k次，点赞29次，收藏52次。nuScenes 数据集 (pronounced /nu:ːsiː:nz/) 是由 Motional (以前称为 nuTonomy) 团队开发的自动驾驶公共大型数据集。nuScenes 数据集的灵感来自于开创性的 KITTI 数据集。nuScenes 是第一个提供自动驾驶车辆整个传感器套件 (6 个摄像头、1 个 LIDAR、5 个 RADAR、GPS、IMU) 数据的大型数据集。与 KITTI 相比，nuScenes 包含的对象注释多了 7 倍。_nuscense数据集
文章浏览阅读535次。我正在实现一个程序,该程序可以侦听特定主题,并在ESP8266发布新消息时对此做出反应.从ESP8266收到新消息时,我的程序将触发回调并执行一系列任务.我在回调函数中发布了两条消息,回到了Arduino正在侦听的主题.但是,仅在函数退出后才发布消息.谢谢您的所有宝贵时间.我试图在回调函数中使用loop(1),超时为1秒.该程序将立即发布该消息,但似乎陷入了循环.有人可以给我一些指针如何在我的回调..._python 函数里面 mqtt调用publish方法 没有效果
文章浏览阅读3.4w次，点赞16次，收藏81次。微软出来了win11预览版系统，很多网友给自己的电脑下载安装尝鲜，不过因为是测试版可能会有比较多bug，又只有英文，有些网友使用起来并不顺畅，因此想要将win11退回win10系统。那么win11怎么装回win10系统呢？今天小编就教下大家win11退回win10系统的方法。方法一：1、首先点击开始菜单，在其中找到“设置”2、在设置面板中，我们可以找到“更新和安全”3、在更新和安全中，找到点击左边栏的“恢复”4、恢复的右侧我们就可以看到“回退到上版本的win10”了。方法二：_安装win10后卸载win11
文章浏览阅读3.3k次，点赞2次，收藏3次。数据定义_sql server菜鸟教程
文章浏览阅读1.9k次。1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]方法一..._给定一个浮点数数组nums(逗号分隔)和一个浮点数目标值target(与数组空格分隔),请
文章浏览阅读152次。提高性能有如下方法1、Cython,用于合并python和c语言静态编译泛型2、IPython.parallel，用于在本地或者集群上并行执行代码3、numexpr，用于快速数值运算4、multiprocessing,python内建的并行处理模块5、Numba，用于为cpu动态编译python代码6、NumbaPro，用于为多核cpu和gpu动态编译python代码为了验证相同算法在上面不同实现..._np.array 测试gpu性能