题解:
倍增+floyd
首先这题比较容易想到是把每个点拆点做dij
但是这样复杂度是knlogn的
这道题的k较大,所以不行
我们考虑到每走一步,其实就是在进行一次floyd
而这个可以看成矩阵乘法
所以可以倍增优化
这样是logk*n^3的
代码:
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define IL inline
#define rint register int
#define me(x) memset(x,0,sizeof(x))
#define fi first
#define se second
#define mid ((h+t)/2)
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define setit set<int>::iterator
const int INF=1e9;
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
int n,m,s,t,cnt;
struct re{
int d[][];
}ys;
re js(re x,re y)
{
re ans;
rep(i,,)
rep(j,,)
ans.d[i][j]=INF;
rep(k,,cnt)
rep(i,,cnt)
rep(j,,cnt)
ans.d[i][j]=min(ans.d[i][j],x.d[i][k]+y.d[k][j]);
return(ans);
}
re qpow(int x)
{
if (x==) return(ys);
re y=qpow(x/);
y=js(y,y);
if (x%) y=js(y,ys);
return(y);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(m); read(s); read(t);
rep(i,,)
rep(j,,)
ys.d[i][j]=INF;
map<int,int>M;
rep(i,,m)
{
int x,y,z;
read(x); read(y); read(z);
int x1,x2;
if (!M[y]) x1=M[y]=++cnt; else x1=M[y];
if (!M[z]) x2=M[z]=++cnt; else x2=M[z];
ys.d[x1][x2]=min(ys.d[x1][x2],x);
ys.d[x2][x1]=min(ys.d[x2][x1],x);
}
re ans=qpow(n);
printf("%d",ans.d[M[s]][M[t]]);
return ;
}
BZOJ 1706的更多相关文章
-
BZOJ 1706: [usaco2007 Nov]relays 奶牛接力跑
Description FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目.至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T < ...
-
bzoj 1706: [usaco2007 Nov]relays 奶牛接力跑——倍增floyd
Description FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目.至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T < ...
-
bzoj 1706: [usaco2007 Nov]relays 奶牛接力跑【矩阵乘法+Floyd】
唔不知道怎么说--大概核心是把矩阵快速幂的乘法部分变成了Floyd一样的东西,非常之神 首先把点离散一下,最多有200个,然后建立邻接矩阵,a[u][v]为(u,v)之间的距离,没路就是inf 然后注 ...
-
BZOJ 1706: [usaco2007 Nov]relays 奶牛接力跑 倍增Floyd
题不难,但是一开始把读入看错了,调了半天qaq~ Code: #include <bits/stdc++.h> #define N 300 #define setIO(s) freopen ...
-
【BZOJ】【1046】/【POJ】【3613】【USACO 2007 Nov】Cow Relays 奶牛接力跑
倍增+Floyd 题解:http://www.cnblogs.com/lmnx/archive/2012/05/03/2481217.html 神题啊= =Floyd真是博大精深…… 题目大意为求S到 ...
-
USACO 刷题记录bzoj
bzoj 1606: [Usaco2008 Dec]Hay For Sale 购买干草——背包 #include<cstdio> #include<cstring> #incl ...
-
Luogu 2886 [USACO07NOV]牛继电器Cow Relays
BZOJ 1706权限题. 倍增$floyd$. 首先这道题有用的点最多只有$200$个,先离散化. 设$f_{p, i, j}$表示经过$2^p$条边从$i$到$j$的最短路,那么有转移$f_{p, ...
-
【BZOJ】1706: [usaco2007 Nov]relays 奶牛接力跑
[题意]给定m条边的无向图,起点s,终点t,要求找出s到t恰好经过n条边的最短路径.n<=10^6,m<=100. [算法]floyd+矩阵快速幂 [题解] 先对点离散化,得到点数N. 对 ...
-
【BZOJ】1297: [SCOI2009]迷路
[题意]给定n个点的有向带边权图,求0到n-1长度恰好为T的路径数.n<=10,T<=10^9,边权1<=wi<=9. [算法]矩阵快速幂 [题解]这道题的边权全部为1时,有简 ...
随机推荐
-
flask_日期和时间
不知道大家有没有发现,在我们学习flask的过程中,post的timestamp字段添加时间时一直用的是datetime.utcnow()来获取时间,但是它获取的时间跟本地时间不一样,下面我们来测试一 ...
-
《OOC》笔记(4)——自动化地将C#代码转化为C代码(结构版)
<OOC>笔记(4)——自动化地将C#代码转化为C代码(结构版) 我在<C表达面向对象语言的机制——C#版>中已经说明了从C#到C的转换方法.这次看<OOC>也是想 ...
-
WebDriver多线程并发
要想多线程并发的运行WebDriver,必须同时满足2个条件,首先你的测试程序是多线程,其次需要用到Selenium Server.下载位置如下图: 下载下来后是一个jar包,需要在命令行中运行.里面 ...
-
私有Pods封装个推SDK功能(解决方案)
一:运用场景 公司中同时有好几个APP在开发,而且每个APP都有使用到集成个推SDK来处理消息的功能,以前的做法是每个APP都去集成并在AppDelegate处理一些SDK的代码,包含个推基础配置.消 ...
-
递推DP URAL 1167 Bicolored Horses
题目传送门 题意:k个马棚,n条马,黑马1, 白马0,每个马棚unhappy指数:黑马数*白马数,问最小的unhappy值是多少分析:dp[i][j] 表示第i个马棚放j只马的最小unhappy值,状 ...
-
(栈的应用5.2.2)POJ 2106 Boolean Expressions(表达式求值)
/* * POJ_2106.cpp * * Created on: 2013年10月30日 * Author: Administrator */ #include <iostream> # ...
-
Deep Learning(深度学习)学习笔记整理系列之(四)
Deep Learning(深度学习)学习笔记整理系列 zouxy09@qq.com http://blog.csdn.net/zouxy09 作者:Zouxy version 1.0 2013-04 ...
-
POJ 2451 Uyuw&#39;s Concert(半平面交nlgn)
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler #include <stdio.h> # ...
-
Android中的单元测试
2015年5月19日 23:10 在Android中,已经内置了Junit所以不需要在导包.只要继承AndroidTestCase类就可以了. 首先需要修改AndroidManifes ...
-
Spring源深和六系列 CreateBean过程
blog宗旨:用图说话. 这一章的图讲述了createBean的过程.到这里spring容器就能够完毕IOC的整个过程,拿到我们须要的对象. 下一章我们接着来看一看AOP完毕的过程. 附:文件夹 Sp ...