Spfa

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

1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 250 Solved: 178 [Submit][Status][Discuss]

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]

1631: [Usaco2007 Feb]Cow Party # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 670 Solved: 493 [Submit][Status][Discuss]

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