当前位置:网站首页>AcWing 1137. 选择最佳线路 题解(最短路)
AcWing 1137. 选择最佳线路 题解(最短路)
2022-07-02 18:27:00 【乔大先生】
AcWing 1137. 选择最佳线路
解题思路:每个起点都跑一次最短路会超时,那就建立一个虚拟初始点,这个初始点距离所有起点的距离都是0,所以这个虚拟初始点到终点的最短路径就是所有起点中最短的最短路
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;
int n, m, T;
int h[N], e[M], ne[M], w[M], idx;
int d[N];
int q[N];
bool st[N];
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++ ;
}
int spfa(){
memset(d, 0x3f, sizeof d);
int hh = 0, tt = 1;
q[0] = 0;
d[0] = 0;
st[0] = true;
while(tt != hh){
int t = q[hh ++ ];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(d[j] > d[t] + w[i]){
d[j] = d[t] + w[i];
if(!st[j]){
q[tt ++ ] = j;
if(tt == N) tt = 0;
st[j] = true;
}
}
}
}
if(d[T] > 1e9) return -1;
else return d[T];
}
int main()
{
while(scanf("%d%d%d", &n, &m, &T) != -1){
memset(h, -1, sizeof h);
idx = 0;
while(m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int w;
cin>>w;
while(w -- ){
int ver;
scanf("%d", &ver);
add(0, ver, 0);
}
cout<<spfa()<<endl;
}
return 0;
}
边栏推荐
- LeetCode 0871. Minimum refueling times - similar to poj2431 jungle adventure
- 使用xml文件打印mybaties-log插件的方式
- [pytorch learning notes] tensor
- 《重构:改善既有代码的设计》读书笔记(下)
- Reading notes of code neatness
- 2022 compilation principle final examination recall Edition
- Chic Lang: completely solve the problem of markdown pictures - no need to upload pictures - no need to network - there is no lack of pictures forwarded to others
- 使用 Cheat Engine 修改 Kingdom Rush 中的金钱、生命、星
- Thread application instance
- Virtual machine initialization script, virtual machine mutual secret key free
猜你喜欢
教程篇(5.0) 10. 故障排除 * FortiEDR * Fortinet 網絡安全專家 NSE 5
仿京东放大镜效果(pink老师版)
高频面试题
PyTorch函数中的__call__和forward函数
潇洒郎:彻底解决Markdown图片问题——无需上传图片——无需网络——转发给他人图片无缺失
Markdown基础语法
450-深信服面经1
Advanced performance test series "24. Execute SQL script through JDBC"
[0701] [论文阅读] Alleviating Data Imbalance Issue with Perturbed Input During Inference
Hospital online inquiry source code hospital video inquiry source code hospital applet source code
随机推荐
ICDE 2023|TKDE Poster Session(CFP)
ORA-01455: converting column overflows integer datatype
Gstore weekly gstore source code analysis (4): black and white list configuration analysis of security mechanism
Reduce -- traverse element calculation. The specific calculation formula needs to be passed in and combined with BigDecimal
Compile oglpg-9th-edition source code with clion
搭建主从模式集群redis
Page title component
新手必看,點擊兩個按鈕切換至不同的內容
Tutoriel (5.0) 10. Dépannage * fortiedr * fortinet Network Security expert NSE 5
注解开发方式下AutowiredAnnotationBeanPostProcessor的注册时机
二进制操作
How to print mybats log plug-in using XML file
xml开发方式下AutowiredAnnotationBeanPostProcessor的注册时机
Horizontal ultra vires and vertical ultra vires [easy to understand]
【测试开发】一文带你了解什么是软件测试
Learn the knowledge points of eight part essay ~ ~ 1
9D电影是怎样的?(+维度空间常识)
教程篇(5.0) 10. 故障排除 * FortiEDR * Fortinet 網絡安全專家 NSE 5
Data dimensionality reduction principal component analysis
Emmet basic syntax