上一波题目 https://www.luogu.org/problem/P1346

是道水题 路口一开始对着的那条路权值为0 其余路权值为1 然后跑一遍最短路就好了

qwq

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define inf 1e9
using namespace std;
const int M=1e5+;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,Ts,Td;
int first[M],cnt;
struct node{int to,next,w;}e[*M];
void ins(int x,int y,int w){e[++cnt]=(node){y,first[x],w}; first[x]=cnt;}
struct qwq{
int id,d;
bool operator<(const qwq&x)const{return x.d<d;}
};
int dis[M];
priority_queue<qwq>q;
void dj(){
for(int i=;i<=n;i++) dis[i]=inf;
dis[Ts]=; q.push((qwq){Ts,dis[Ts]});
while(!q.empty()){
qwq x=q.top(); q.pop();
if(x.d<dis[x.id]) continue;
for(int i=first[x.id];i;i=e[i].next){
int now=e[i].to;
if(dis[now]>dis[x.id]+e[i].w){
dis[now]=dis[x.id]+e[i].w;
q.push((qwq){now,dis[now]});
}
}
}
}
int main(){
int k,x;
n=read(); Ts=read(); Td=read();
for(int i=;i<=n;i++){
k=read();
for(int j=;j<=k;j++){
x=read();
if(j==) ins(i,x,);
else ins(i,x,);
}
}
dj();
if(dis[Td]==inf) puts("-1");
else printf("%d\n",dis[Td]);
return ;
}

最新文章

  1. 前端HTML之页面结构
  2. Android学习第二天-android常用命令
  3. lua 例子
  4. 阿里云服务器Linux CentOS安装配置(九)shell编译、打包、部署
  5. MFC操作excel
  6. Java小游戏贪吃蛇
  7. R语言入门系列1--数学狗还是做数据好了
  8. HTML + JS随机抽号。
  9. 3个常用基于Linux系统命令行WEB网站浏览工具(w3m/Links/Lynx)
  10. C语言细节——献给入门者(三)
  11. MVC使用的MetaModel代码生成器模板
  12. HTTP 错误 404.3 - Forbidden
  13. jconsole线程面板中的阻塞总数和等待总数(转)
  14. UISwitch 开关控件
  15. tab切换插件开发
  16. Java大数据人才应用领域广,就业薪酬高
  17. Java学习笔记14(面向对象七:final、static)
  18. 5.5Python数据处理篇之Sympy系列(五)---解方程
  19. QTP自动化测试-打开运行报告
  20. Altium Designer 17 ------ 多层板设计

热门文章

  1. 2019 Multi-University Training Contest 1 - 1004 - Vacation - 二分 - 思维
  2. 【JMeter5.0】Mac安装JDK和JMeter5
  3. 同一客户端多个git账号的配置
  4. day50 初识JavaScript
  5. CMS(1)
  6. go语言从例子开始之Example32.打点器
  7. C++链接器
  8. leetcode-167周赛-1290-二进制链表转整数
  9. php is_file()函数 语法
  10. JavaScript中的编码解码