当前位置:网站首页>练习40,小蓝的旅行【最短路】
练习40,小蓝的旅行【最短路】
2022-08-02 08:32:00 【ILECY】
根据题意,我们知道只能从未做核酸的城市到做核酸的城市或者从做核酸的城市到未做核酸的城市,所以我们可以将每个点分别当成未做核酸的和做了核酸的,然后分别建边求最短路
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define NOTLE ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define T int TT;cin >> TT;while (TT--)
#define lint long long
#define pb push_back
#define eb emplace_back
int last[800010],ne[800010],to[800010],w[800010],cnt=0; //要开4倍(无向图+是否做核酸
int n,m,x;
lint d[200010],vis[200010]={0};
void add(int a,int b,int c){ //链式前向星存图
ne[++cnt]=last[a];
to[cnt]=b;
w[cnt]=c;
last[a]=cnt;
}
void SPFA(){
memset(d,INF,sizeof(d));
queue<int> q;
q.push(1);
d[1]=0,vis[1]=1;
while(!q.empty()){
int now=q.front();
q.pop();
vis[now]=0;
for(int i=last[now];i;i=ne[i]){
if(d[to[i]]>d[now]+w[i]){
d[to[i]]=d[now]+w[i];
if(!vis[to[i]]){
q.push(to[i]);
vis[to[i]]=1;
}
}
}
}
}
int main(){
NOTLE;
cin >> n >> m >> x;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
if(a==1){ //一开始是没有做核酸的
add(a,b+n,c+x);
add(b+n,a,c);
}
else{ //由于是无向图存两遍,而且要保证只能从有→无或无→有
add(a+n,b,c);
add(b,a+n,c+x);
add(a,b+n,c+x);
add(b+n,a,c);
}
}
SPFA();
cout << min(d[n],d[n+n]) << endl;
return 0;
}
边栏推荐
- Wang Xuegang - compiled shipment line file
- R语言plotly可视化:使用plotly可视化模型预测真阳性率(True positive)TPR和假阳性率(False positive)FPR在不同阈值(threshold)下的曲线
- Redisson报异常attempt to unlock lock, not locked by current thread by node id解决方案
- Flink 监控指南 被动拉取 Rest API
- C Language Basics_Union
- 四字节的float比八字结的long范围大???
- Redisson的看门狗机制
- PostgreSQL learning summary (11) - PostgreSQL commonly used high-availability cluster solutions
- Redisson实现分布式锁
- 第3周学习:ResNet+ResNeXt
猜你喜欢
随机推荐
Biotin - LC - Hydrazide | CAS: 109276-34-8 | Biotin - LC - Hydrazide
Qt读取文件中内容(通过判断GBK UTF-8格式进行读取显示)
The packet capture tool Charles modifies the Response step
Wang Xuegang - compiled shipment line file
OneinStack多版本PHP共存
What is the function of page directive contentPage/pageEncoding in JSP page?
编程与哲学(2)——输出是为了更好的输入
UVM之sequence机制
构建Flink第一个应用程序
如何做好项目管理
Codeforces Round #811 (Div. 3)无DF
ORBSLAM代码阅读
【C】关于柔性数组.简要的谈谈柔性数组
自定义table表格
JSP页面中page指令contentPage/pageEncoding具有什么功能呢?
Redisson报异常attempt to unlock lock, not locked by current thread by node id解决方案
EPSANet: An Efficient Pyramid Split Attention Block on Convolutional Neural Network
Installation and use of pnpm
PostgreSQL学习总结(11)—— PostgreSQL 常用的高可用集群方案
Flink 程序剖析