[JLOI2011]飞行路线 (分层图,最短路)
2024-08-30 05:56:26
题目链接
Solution
建立 \(k+1\) 层图跑 \(Dijkstra\) 就好了.
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200008;
int n,m,k,s,t;
struct sj{
int to;
int next;
int w;
}a[maxn*10];
int head[maxn],size;
ll dis[maxn],dist[maxn];
void add(int x,int y,int w)
{
a[++size].to=y;
a[size].next=head[x];
head[x]=size;
a[size].w=w;
}
int read()
{
char ch=getchar(); int f=1,w=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}
return f*w;
}
struct node {
int u;ll d;
bool operator <(const node& rhs) const {
return d>rhs.d;
}
};
inline void Dijkstra()
{
memset(dis,127,sizeof(dis));
dis[s]=0;
priority_queue<node> q;
q.push((node){s,0});
while(!q.empty())
{
node xx=q.top(); q.pop();
int u=xx.u,d=xx.d;
if(d!=dis[u])continue;
for(int i=head[u];i;i=a[i].next)
{
int tt=a[i].to,w=a[i].w;
if(dis[u]+w<dis[tt])
{
dis[tt]=dis[u]+w;
q.push((node){tt,dis[tt]});
}
}
}
}
void pre(int x,int y,int w)
{
for(int i=0;i<=k;i++)
add(x+n*i,y+n*i,w),
add(y+n*i,x+n*i,w);
for(int i=0;i<k;i++)
add(x+n*i,y+n*i+n,0),
add(y+n*i,x+n*i+n,0);
}
int main()
{
n=read(); m=read(); k=read();
s=read(); t=read();
for(int i=1;i<=m;i++)
{
int x,y,w;
x=read();
y=read();
w=read();
pre(x,y,w);
}
for(int i=0;i<=k;i++)
add(t+i*n,n*(k+1)+1,0);
Dijkstra();
cout<<dis[n*(k+1)+1]<<endl;
}
最新文章
- 【NLP】Python NLTK获取文本语料和词汇资源
- asp.net程序集冲突解决笔记(未能加载文件或程序集";XXXXXXXXX";)
- JavaScript Patterns 4.2 Callback Pattern
- sql windows server2008 全套激活码
- Perl Print Win32 Console Windows 控制台 print Unicode 问题
- 关于Linux的windows目录的挂载
- binder
- Solr Update备注
- C语言链表各类操作详解
- 【原创】-- C# 点滴积累 -- String
- FPM定制RPM包实践
- Spring Cloud 组件 —— eureka
- 安装pwntools及对于解决问题方法搜索的经验总结
- xibai的PCI卡在英文系统上安装报错
- 万年不变话题cookie,简单总结
- jQuery 替换元素
- HTTP请求返回状态码详解
- 对io进行分流
- linux工具大全
- oracle 中 cursor 与refcursor及sys_refcursor的区别 (转载)
热门文章
- 字符编码ANSI和ASCII区别、Unicode和UTF-8区别
- 解决TS报错Property &#39;style&#39; does not exist on type &#39;Element&#39;
- javaweb基础(23)_jsp自定义标签
- C/C++字符串笔试知识点及实例
- c++ 用指针操作数组
- 201621123080《Java程序设计》第三周学习总结
- iPhone如何设置自定义铃声?无需连接电脑,轻松几步就搞定!
- Goroutine 中执行匿名函数 坑
- sql 单表/多表查询去除重复记录
- selection problem-divide and conquer