SPFA

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 culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. NOTE: Do not declare a variable named exactly ’time’. This will reference the system call and never give you the results you really want.

uva10986题目链接 题意：裸的spfa. 思路：模板，1A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月25日 星期三 03时25分27秒 4File Name :code/uva/10986.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E4+7; 34int n,m; 35int S,T; 36vector < pi > edge[N]; 37 38int d[N]; 39bool inq[N]; 40bool spfa( int s,int t) 41{ 42 ms(d,0x3f); 43 ms(inq,false); 44 queue<int>q; 45 q.push(s); 46 inq[s] = true; 47 d[s] = 0; 48 49 while (!q.empty()) 50 { 51 int u = q.front(); 52 q.pop(); 53 inq[u] = false; 54 55 int siz = edge[u].size(); 56 57 for ( int i = 0 ; i < siz ; i++) 58 { 59 int v = edge[u][i].fst; 60 if (d[v]>d[u] + edge[u][i].sec) 61 { 62 d[v] = d[u] + edge[u][i].sec; 63 if (inq[v]) continue; 64 inq[v] = true; 65 q.push(v); 66 } 67 } 68 } 69 return d[t]!=inf; 70} 71int main() 72{ 73 #ifndef ONLINE_JUDGE 74 freopen("code/in.txt","r",stdin); 75 #endif 76 ios::sync_with_stdio(false); 77 int TT; 78 cin>>TT; 79 int cas = 0 ; 80 while (TT--) 81 { 82 cin>>n>>m>>S>>T; 83 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 84 for ( int i = 1 ; i <= m ; i++) 85 { 86 int u,v,w; 87 cin>>u>>v>>w; 88 edge[u].push_back(make_pair(v,w)); 89 edge[v].push_back(make_pair(u,w)); 90 } 91 92 if (spfa(S,T)) 93 { 94 printf("Case #%d: %d\n",++cas,d[T]); 95 } 96 else 97 { 98 printf("Case #%d: unreachable\n",++cas); 99 } 100 101 } 102 103 #ifndef ONLINE_JUDGE 104 fclose(stdin); 105 #endif 106 return 0; 107}

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)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。

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牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？ Input # 第1行：三个用空格隔开的整数.

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