关键词：
P1613 跑路
题目描述
小\(A\)的工作不仅繁琐，更有苛刻的规定，要求小\(A\)每天早上在\(6:00\)之前到达公司，否则这个月工资清零。可是小\(A\)偏偏又有赖床的坏毛病。于是为了保住自己的工资，小\(A\)买了一个十分牛B的空间跑路器，每秒钟可以跑\(2^k\)千米（\(k\)是任意自然数）。当然，这个机器是用\(long\) \(int\)存的，所以总跑路长度不能超过\(max\) \(long\) \(int\)千米。小\(A\)的家到公司的路可以看做一个有向图，小\(A\)家为点\(1\)，公司为点\(n\)，每条边长度均为一千米。小\(A\)想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证\(1\)到\(n\)至少有一条路径。
输入输出格式
输入格式：
第一行两个整数\(n\),\(m\)，表示点的个数和边的个数。
接下来m行每行两个数字\(u\),\(v\)，表示一条\(u\)到\(v\)的边。
输出格式：
一行一个数字，表示到公司的最少秒数。
说明
\(50\)%的数据满足最优解路径长度\(<=1000\)；
\(100\)%的数据满足\(n<=50\)，\(m<=10000\)，最优解路径长度\(<=\) \(max\) \(long\) \(int\)。
首先，要确保自己的语文水平苟的住，这个鬼机器，每秒跑\(2^kkm\)的话是要跑刚好那么长的，不能多也不能少。
那么岂不是代表，只有长为\(2^kkm\)的链才算是有效边吗?
我们把所有有效边连上，跑最短路不就行了嘛。
如何求有效边？
\(2^k?\)有没有想到什么？
\(2^k=2^k-1+2^k-1?\)
对，就是倍增啊！
令\(g[u][v][j]\)代表点\(u\)到点\(v\)存在或不存在长度为\(2^j\)的边。
当\(g[u][k][j-1]\)和\(g[k][v][j-1]\)同时存在时，
\(g[u][v][j]\)存在。（\(k\)是枚举的一维）
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=52;
int g[N][N][70],n,m;
//g[i][j][k]表示i点到j点存在边权为2^k的路
int g0[N][N];
int read()
int x=0;char c=getchar();
while(c<‘0‘||c>‘9‘) c=getchar();
while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘;c=getchar();
return x;
queue <int > q;
int used[N],dis[N];
void spfa()
memset(used,0,sizeof(used));
used[1]=1;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(1);
while(!q.empty())
int u=q.front();
q.pop();
used[u]=0;
for(int v=1;v<=n;v++)
if(g0[u][v]&&dis[v]>dis[u]+g0[u][v])
dis[v]=dis[u]+g0[u][v];
if(!used[v])
used[v]=1;
q.push(v);
int main()
memset(g,0,sizeof(g));
memset(g0,0,sizeof(g0));
n=read(),m=read();
int u,v;
for(int i=1;i<=m;i++)
u=read(),v=read();
g[u][v][0]=1;
//f[u][v][0]=v;
for(int j=1;j<=64;j++)
for(int k=1;k<=n;k++)
for(u=1;u<=n;u++)
for(v=1;v<=n;v++)
if(g[u][k][j-1]&&g[k][v][j-1])
g[u][v][j]=1;
for(u=1;u<=n;u++)
for(v=1;v<=n;v++)
for(int j=0;j<=64;j++)
if(g[u][v][j])
g0[u][v]=1;
break;
spfa();
printf("%d\n",dis[n]);
return 0;
2018.5.2
洛谷p1691解题报告
P1691有重复元素的排列问题题目描述设\(R=r_1,r_2,……,r_n\)是要进行排列的\(n\)个元素。其中元素\(r_1,r_2,……,r_n\)可能相同。使设计一个算法，列出\(R\)的所有不同排列。给定\(n\)以及待排列的\(n\)个元素。计算出这\(n\)个元素的所... 查看详情
洛谷p1450解题报告
P1450.硬币购物题目描述硬币购物一共有\(4\)种硬币。面值分别为\(c1,c2,c3,c4\)。某人去商店买东西，去了\(tot\)次。每次带\(d_i\)枚\(c_i\)硬币，买\(s_i\)的价值的东西。请问每次有多少种付款方法。输入输出格式输入格式：第一行\(c_1,... 查看详情
洛谷p1129解题报告
题目描述小$Q$是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个$N*N$黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作... 查看详情
洛谷p3853解题报告
P3853路标设置题目背景B市和T市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最... 查看详情
洛谷p1490解题报告
P1490买蛋糕题目描述野猫过生日，大家当然会送礼物了（咳咳，没送礼物的同志注意了哈！！），由于不知道送什么好，又考虑到实用性等其他问题，大家决定合伙给野猫买一个生日蛋糕。大家不知道最后要买的蛋糕的准确价格... 查看详情
洛谷p2764解题报告(代码片段)
P2764最小路径覆盖问题问题描述：给定有向图\(G=(V,E)\)。设\(P\)是\(G\)的一个简单路（顶点不相交）的集合。如果\(V\)中每个顶点恰好在\(P\)的一条路上，则称\(P\)是\(G\)的一个路径覆盖。\(P\)中路径可以从\(V\)的任何一个顶点开始，... 查看详情
洛谷p1879解题报告(代码片段)
P1879[USACO06NOV]玉米田CornFields题目描述农场主\(John\)新买了一块长方形的新牧场，这块牧场被划分成\(M\)行\(N\)列\((1≤M≤12;1≤N≤12)\)，每一格都是一块正方形的土地。\(John\)打算在牧场上的某几格里种上美味的草，供他的奶牛们享... 查看详情
洛谷p2725解题报告(代码片段)
P2725邮票Stamps题目背景给一组N枚邮票的面值集合（如，1分，3分）和一个上限K——表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。题目描述例如，假设有1分和3分的邮票；你最多可以贴5张邮票。很容易贴出1到5... 查看详情
洛谷p2466sue的小球解题报告(代码片段)
P2466[SDOI2008]Sue的小球题目描述Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一个秘密... 查看详情
洛谷p2469[sdoi2010]星际竞速解题报告
题目描述10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座α星的悠悠也是其中之一。赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗... 查看详情
洛谷p1053音乐会的等待解题报告(代码片段)
P1823音乐会的等待题目描述\(N\)个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人\(A\)和\(B\)，如果他们是相邻或他们之间没有人比\(A\)或\(B\)高，那么他们是... 查看详情
洛谷p3253[jloi2013]删除物品解题报告(代码片段)
P3253[JLOI2013]删除物品题目描述箱子再分配问题需要解决如下问题：（1）一共有\(N\)个物品，堆成\(M\)堆。（2）所有物品都是一样的，但是它们有不同的优先级。（3）你只能够移动某堆中位于顶端的物品。（4）你可以把任意一堆... 查看详情
解题报告合并果子(代码片段)
题目来源洛谷P1090 [NOIP2004提高组]合并果子/[USACO06NOV]FenceRepairG-洛谷题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，... 查看详情
解题报告中位数(代码片段)
题目来源洛谷P1168 中位数-洛谷题目描述给出一个长度为N的非负整数序列A[i]，对于所有1≤k≤(N+1)/2，输出A[1],A[3],…,A[2k-1]的中位数。即前1，3，5，……个数的中位数。输入输出格式输入格式：输入文件... 查看详情
noip1999普及组解题报告
不知怎么地，洛谷的noip1999普及组的题和以前考的不一样/雾回文数分析：一道高精度加法的模拟题，注意还有16进制。#include<iostream>#include<algorithm>#include<cstring>#include<cmath>usingnamespacestd;constintmaxn=150;intn,len=0,a[ 查看详情
noip2000普及组解题报告
/雾noip2000发生了什么？为什么洛谷上就一道题-- 计算器的改良分析：字符串模拟题。记录分别记录等式两边的系数与常数即可。以前在codevs上做过，也就直接把代码贴上来了。#include<iostream>#include<algorithm>#include<cst... 查看详情
noip2016普及组复赛解题报告
提高组萌新，DAY1DAY2加起来骗分不到300，写写普及组的题目聊以自慰。（附：洛谷题目链接 T1：https://www.luogu.org/problem/show?pid=1909 T2：https://www.luogu.org/problem/show?pid=2010 T3：https://www.luogu.org/ 查看详情
[sdoi2009]hh的项链解题报告
原题目：洛谷P1972题目描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。... 查看详情