问题描述
For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.
Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.
To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.
Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.
输入格式
* Line 1: Four space-separated integers: N, T, S, and E
* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i
输出格式
* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.
样例输入
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
样例输出
10
题目大意
给出一张无向连通图,求S到E经过k条边的最短路。
解析
倍增Floyd模版题。利用矩阵快速幂的形式可以在\(log\)的时间内处理经过k条路径的最短路。
虽然一共有1000000个点,但是因为只有100条边,可以直接用100条边的端点建图,离散化编号即可。
代码
#include <iostream>
#include <cstdio>
#define int long long
#define N 1000002
using namespace std;
const int inf=1<<30;
struct Matrix{
int a[500][500];
}S;
int n,m,s,t,i,j,id[N],cnt;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
Matrix mult(Matrix a,Matrix b)
{
Matrix c;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++) c.a[i][j]=inf;
}
for(int k=1;k<=cnt;k++){
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++) c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
}
}
return c;
}
Matrix poww(Matrix a,int b)
{
b--;
Matrix ans=a,base=a;
while(b){
if(b&1) ans=mult(ans,base);
base=mult(base,base);
b>>=1;
}
return ans;
}
signed main()
{
n=read();m=read();s=read();t=read();
for(i=1;i<=2*m;i++){
for(j=1;j<=2*m;j++) S.a[i][j]=inf;
}
for(i=1;i<=m;i++){
int w=read(),u=read(),v=read();
if(!id[u]) id[u]=++cnt;
if(!id[v]) id[v]=++cnt;
S.a[id[u]][id[v]]=S.a[id[v]][id[u]]=w;
}
Matrix ans=poww(S,n);
cout<<ans.a[id[s]][id[t]]<<endl;
return 0;
}
[洛谷P2886] 牛继电器Cow Relays的更多相关文章
-
洛谷 [P2886] 牛继电器Cow Relays
最短路 + 矩阵快速幂 我们可以改进矩阵快速幂,使得它适合本题 用图的邻接矩阵和快速幂实现 注意 dis[i][i] 不能置为 0 #include <iostream> #include ...
-
洛谷P2886牛继电器
传送门啦 倍增 $ Floyd $ 注意结构体里二维数组不能开到 $ 2000 $ #include <iostream> #include <cstdio> #include ...
-
P2886 [USACO07NOV]牛继电器Cow Relays
题目描述 For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race ...
-
[USACO07NOV]牛继电器Cow Relays (最短路,DP)
题目链接 Solution 非正解 似乎比较蛇啊,先个一个部分分做法,最短路+\(DP\). 在求最短路的堆或者队列中存储元素 \(dis_{i,j}\) 代表 \(i\) 这个节点,走了 \(j\) ...
-
洛谷P2886 [USACO07NOV]牛继电器Cow Relays
题意很简单,给一张图,把基本的求起点到终点最短路改成求经过k条边的最短路. 求最短路常用的算法是dijkstra,SPFA,还有floyd. 考虑floyd的过程: c[i][j]=min(c[i][ ...
-
洛谷 P2886 [USACO07NOV]牛继电器Cow Relays
题面 解题思路 ## floyd+矩阵快速幂,跟GhostCai爷打赌用不用离散化,最后完败..GhostCai真是tql ! 有个巧妙的方法就是将节点重新编号,因为与节点无关. 代码 #includ ...
-
[LUOGU] P2886 [USACO07NOV]牛继电器Cow Relays
https://www.luogu.org/problemnew/show/P2886 给定无向连通图,求经过k条边,s到t的最短路 Floyd形式的矩阵乘法,同样满足结合律,所以可以进行快速幂. 离 ...
-
luogu题解 P2886 【牛继电器Cow Relays】-经过K边最短路&;矩阵
题目链接: https://www.luogu.org/problemnew/show/P2886 Update 6.16 最近看了下<算法导论>,惊奇地发现在在介绍\(APSP\) \( ...
-
[USACO07NOV]牛继电器Cow Relays
题目描述 给出一张无向连通图,求S到E经过k条边的最短路. 输入输出样例 输入样例#1: 2 6 6 4 11 4 6 4 4 8 8 4 9 6 6 8 2 6 9 3 8 9 输出样例#1: 10 ...
随机推荐
-
.Net Core下如何管理配置文件
一.前言 根据该issues来看,System.Configuration在.net core中已经不存在了,那么取而代之的是由Microsoft.Extensions.Cnfiguration.XX ...
-
[Redux] Normalizing the State Shape
We will learn how to normalize the state shape to ensure data consistency that is important in real- ...
-
基于xml文件实现系统属性配置管理
文章标题:基于xml文件实现系统属性配置管理 . 文章地址: http://blog.csdn.net/5iasp/article/details/11774501 作者: javaboy2012 E ...
-
vs2010根据字符串内容添加断点
在vs中我们可以直接用表达式.数值型比较直接用操作符即可. 如i==2,i<2; 但是字符型比较呢? 加入我们有一个名为string的变量,定义如下: char *string="Tw ...
-
UVa 10034 - Freckles
题目大意:给出n个点的坐标(x,y),要求用线段将n个点连接起来,求最小的线段和. 最小生成树问题,用Kruskal算法进行求解,其中用到了并查集.将所有的点连接,构成一张图,对每一条边进行编号,两点 ...
-
解决Perhaps you are running on a JRE rather than a JDK?问题
Maven-No compiler is provided in this environment. Perhaps you are running on a JRE rather than a JD ...
-
微信小程序开发平台新功能「云开发」快速上手体验
微信小程序开发平台刚刚开放了一个全新的功能:云开发. 简单地说就是将开发人员搭建微信小程序后端的成本再次降低,此文刚好在此产品公测时,来快速上手看看都有哪些方便开发者的功能更新. 微信小程序一直保持一 ...
-
Python-css高级
1. 伪类和伪元素 1. 伪类 1. :link 2. :visited 3. :hover (重要) 4. :active 5. :focus(input标签获取光标焦点) 2. 伪元素 1. :f ...
-
module.exports用法
module.exports 对象是由模块系统创建的.在我们自己写模块的时候,需要在模块最后写好模块接口,声明这个模块对外暴漏声明内容,module.exports提供了暴漏接口的方法. 1.返回一个 ...
-
redis conf 详解
2.8配置 # Redis configuration file example # Note on units: when memory size is needed, it is possible ...