首页 > 其他分享 >10.18

10.18

时间:2022-10-18 22:12:56浏览次数:156  
标签:10 le int 样例 10.18 dep dis

[COCI2021-2022#4] Autobus

题目描述

在一个国家里有 \(n\) 座城市。这些城市由 \(m\) 条公交线路连接,其中第 \(i\) 条线路从城市 \(a_i\) 出发,到 \(b_i\) 停止,路程中耗时 \(t_i\) 分钟。

Ema 喜欢旅行,但她并不喜欢在公交线路之间换乘。在旅行过程中,她希望最多只需坐 \(k\) 个不同的公交线路。

Ema 想知道,从城市 \(c_i\) 到城市 \(d_i\) 的最短旅行时间是多少(最多坐 \(k\) 个不同的公交线路)。

输入格式

第一行包含两个整数 \(n,m\),分别表示城市的数量和公交车线路的数量。

接下来 \(m\) 行,第 \(i+1\) 包含三个整数 \(a_i,b_i,t_i\),分别表示第 \(i\) 条公交车线路的起点、终点和从起点到终点所需的时间。

接下来一行包含两个整数 \(k,q\),最大坐的不同公交线路的个数和问题题的个数。

接下来 \(q\) 行,第 \(m+j+3\) 行包含两个整数 \(c_j,d_j\),表示询问从城市 \(c_j\) 到城市 \(d_j\) 的最短旅行时间。

输出格式

输出包含 \(q\) 行,第 \(i\) 行包含一个整数,表示从城市 \(c_i\) 到城市 \(d_i\) 的最短旅行时间。

样例 #1

样例输入 #1

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3

样例输出 #1

10
-1
0

样例 #2

样例输入 #2

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
2 3
1 4
4 2
3 3

样例输出 #2

6
4
0

样例 #3

样例输入 #3

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
3 3
1 4
4 2
3 3

样例输出 #3

3
4
0

提示

【样例解释】

每个样例中的答案都已经标记在图中。

【数据规模与约定】

本题采用子任务捆绑测试。

  • Subtask 1(15 pts):\(k ≤ n ≤ 7\)。
  • Subtask 2(15 pts):\(k ≤ 3\)。
  • Subtask 3(25 pts):\(k ≤ n\)。
  • Subtask 4(15 pts):没有额外限制。

对于 \(100\%\) 的数据,\(2\le n \le 70,1\le m,t_i\le 10^6,1\le a_i,b_i,c_j,d_j\le n,1\le k\le10^9,1\le q \le n^2\)。

【提示与说明】

本题分值按 COCI 原题设置,满分 \(70\)。

题目译自 COCI2021-2022 CONTEST #4 T2 Autobus。

分析

最短路,图论
就是一个有深度限制的最短路
每个点跑 \(dij\) ,并且对宽搜深度限制
详见代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=5000;
const int maxn=100010;

template<typename T>void read(T &x)
{
	x=0;char c=getchar();T neg=0;
	while(!isdigit(c))neg|=!(c^'-'),c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(neg)x=(~x)+1;
}
template<typename T>void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar((x-x/10*10)^48);
	return ;
}

int n,m,k,Q,Ans;
int e[72][72];

int tot,head[N],ver[N],nex[N],edge[N];
void add(int u,int v,int w){ ver[++tot]=v; nex[tot]=head[u]; head[u]=tot; edge[tot]=w; }

int dis[72],dep[72];
struct node{
	int dep,id,dis;
	bool operator<(const node x)const{  return dis>x.dis;   };// 按照 dis 进行小根堆 
};
int vis[72][72],cnt;
int BFS(int st,int t,int lim)
{
	priority_queue<node>q;// 用堆优化,取出每次距离最短的点 
	memset(vis,127,sizeof vis);//初始化为极大值 
	// vis 记录当前 起始点为 u 时 节点 i 在 j 层的距离 u 的最小距离 
	node tmp;
	tmp.dep=1;tmp.id=st;tmp.dis=0;
	// dis 的定义为距离起始点 的最小距离 
	q.push(tmp);//把起始点丢进去进行搜索 
	while(q.size())
	{
		node x=q.top(); q.pop();
		int id=x.id, dep=x.dep, dis=x.dis;
		if(id==t) return x.dis;//如果可以取到,且t第一次出现一定 最小距离 
		if(dep>=lim+1) continue;//如果这个取出的点已经是最大深度,他的子节点就不需要入堆,之后的子节点深度就必然超出 limit 
		for(int i=head[id];i;i=nex[i])
		{
			int v=ver[i],w=edge[i];
			if(!vis[v][dep+1]||dis+w<vis[v][dep+1])
			{
				//v 在 dep+1 这种情况要么没走过
				// 或是 当前出现更优情况才重新遍历
				 
				vis[v][dep+1]=dis+w;//更新 
				node tmp;
				tmp.id=v;
				tmp.dis=dis+w;
				tmp.dep=dep+1;
				q.push(tmp);// 拓展 
			}
		}
	}
	return -1;
}
signed main()
{
	read(n),read(m);
	memset(e,127,sizeof e);
	int inf=e[0][0];
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		read(u),read(v),read(w);
		if(u==v) continue;// 排除自环 
		e[u][v]=min(e[u][v],w);// 除去重边 
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j) continue;
			if(e[i][j]!=inf) add(i,j,e[i][j]);//建出最优边 
		}
	}
//	for(int i=1;i<=n;i++) add(0,i,0);//没什么用 
	
	read(k), read(Q);
	for(int i=1;i<=Q;i++)
	{
		int u;int v;
		read(u),read(v);
		Ans=BFS(u,v,k);//记录答案 
		if(Ans>=0) wr(Ans),putchar('\n');
		else putchar('-'),putchar('1'),putchar('\n');
	}
	return 0;
}

标签:10,le,int,样例,10.18,dep,dis
From: https://www.cnblogs.com/llwwll/p/16804390.html

相关文章

  • 2022.10.18 CSP2022 模拟赛五
    旅行路线Source:CF459E。憨憨题。按\(w\)排序后,考虑DP,设\(f_u\)表示目前在点\(u\),可以走出的最长路线。按阶段转移的时候稍微注意一下相同边权的处理,具体的,开一个......
  • 【闲话】2022.10.18
    今天中午是world.execute(me),好欸今天考试本来看完题之后就想着直接爆零得了一点思路都没有,真的要放弃了然后最后还是侥幸切了两道(我跟你说我T1结论是试出来的你......
  • 10.18
    finalshell输入showdatabases;报错HiveExceptionjava.lang.RuntimeException:Unabletoinstantiateorg.apache.hadoop.hive.ql.metadata.SessionHiveMetaStoreClient......
  • 10.18
    今日内容1.索引取值与迭代取值的差异2.模块简介3.模块的分类4.导入模块的两种句式5.导入模块的补充说明6.循环导入问题7.判断文件类型8.模块的查找顺序9.绝对导入......
  • 【2022.10.18】Linux入门基础(1)
    内容概要主题:linux运维(记)linux基础几乎以记忆为主(理论知识)运维的本质服务器介绍服务器品牌服务器参数服务器组件磁盘阵列虚拟化技术虚拟化软件安装虚......
  • [2022.10.18]构造器
    类中的构造器也称为构造方法,是在进行创建对象的时候必须要调用的。并且构造器有以下两个特点:1.必须和类的名字相同2.必须没有返回类型,也不能写void构造器:1.和类名相同2.......