cf689B题目链接

题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近）

思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M...因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 250  Solved: 178 [Submit][Status][Discuss]

Description

A crime has been comitted: a load of grain has been taken from the barn by one of FJ's cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the …

uva10986题目链接 题意：裸的spfa.

思路：模板，1A.

/* ***********************************************
Author :111qqz
Created Time :2016年05月25日 星期三 03时25分27秒
File Name :code/uva/10986.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include …

poj2949 题目链接 题意：我们有 n 个 (n<=100000) 字符串,每个字符串都是由 a~z 的小写英文字 母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两字符相 匹配,那么我们称 A 与 B 能相连(注意: A 能与 B 相连不代表 B 能与 A 相连)。 我们希望从给定的字符串中找出一些,使得他们首尾相接形成一个环串(一个串首尾相连也算) 我们想要使这个环串的平均长度最长。

poj 1860 题目链接

题意：有n种货币，m个货币交易点，每个货币交易点只能是两种货币之间交换，给出两个方向的汇率和手续费。初始拥有数量v的货币s,问能否经过一些py交易，使得最后手里的货币s比v多。

poj1932题目链接

题意：初始在点1，有100点能量，然后每个点有一个能量值【-100,100】，经过某个点会加上这个点的能量值，问能否找到一条到点n且的路线，且路径任何点的能量值一直为正。一共不超过100个点。

poj 1511 题目链接 题意：和那道奶牛的舞会类似，要求所有点到点1的距离和加上1点到所有点的距离和。 思路：正反存边建两次图，跑两次spfa. 然而用vector会TLE....所以去学习了新的建图方式。。。也就是链式前向星：链式前向星（边表）学习链接 也叫边表。

1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 1325  Solved: 570 [Submit][Status][Discuss]

Description

Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话 …

1631: [Usaco2007 Feb]Cow Party

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 670  Solved: 493 [Submit][Status][Discuss]

Description

    农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？

hdu 3790 题目链接

题意：给出n个点m条无向边，每条边有一个距离和一个花费。给出s,t。问从s到t的最短距离以及最短距离时的最小花费。当有多个距离最短的方案时，选取花费最少的。