【BZOJ】2015: [Usaco2010 Feb]Chocolate Giving(spfa)
2015 BZOJ SPFA Feb
2023-09-27 14:22:21 时间
http://www.lydsy.com/JudgeOnline/problem.php?id=2015
这种水题真没啥好说的。。
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) #define for1(i,a,n) for(int i=(a);i<=(n);++i) #define for2(i,a,n) for(int i=(a);i<(n);++i) #define for3(i,a,n) for(int i=(a);i>=(n);--i) #define for4(i,a,n) for(int i=(a);i>(n);--i) #define CC(i,a) memset(i,a,sizeof(i)) #define read(a) a=getint() #define print(a) printf("%d", a) #define dbg(x) cout << #x << " = " << x << endl #define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; } inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } inline const int max(const int &a, const int &b) { return a>b?a:b; } inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=55005, Q=N*10, oo=~0u>>2; int q[Q], front, tail, d[N], vis[N], ihead[N], cnt, n, x, m; struct ED { int to, w, next; }e[Q]; void add(int u, int v, int w) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].w=w; e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u; e[cnt].w=w; } void spfa() { q[tail++]=1; for1(i, 2, n) d[i]=oo; vis[1]=1; while(front!=tail) { int v, u=q[front++]; if(front==Q) front=0; vis[u]=0; for(int i=ihead[u]; i; i=e[i].next) if(d[v=e[i].to]>d[u]+e[i].w) { d[v]=d[u]+e[i].w; if(!vis[v]) { vis[v]=1; q[tail++]=v; if(tail==Q) tail=0; } } } } int main() { read(n); read(m); read(x); for1(i, 1, m) { int u=getint(), v=getint(), w=getint(); add(u, v, w); } spfa(); for1(i, 1, x) { int u=getint(), v=getint(); printf("%d\n", d[u]+d[v]); } return 0; }
相关文章
- NLP-信息抽取-NER-2015:BiLSTM-CRF【Bidirectional LSTM-CRF Models for Sequence Tagging】
- Gartner:2015年全球安全软件市场增长3.7%
- IDC:2015年中国社交化移动办公软件市场呈爆发式增长
- 2015第三季度以太网交换机市场增长2%
- 飞康荣获 SVC 2015 年度最佳产品大奖
- 2015年大数据顶尖职位必备的9项技能
- 百度.搜狐...2015产品经理面试题
- CITE 2015聚焦车联网 智能汽车再掀热潮
- 2015中国互联网大会 共同探讨创新创业潮
- 2015新浪商业思想OpenDay 解密大数据营销
- Shell脚本编程入门(一) 分类: 学习笔记 linux ubuntu 2015-07-09 21:06 29人阅读 评论(0) 收藏
- ubuntu中安装jdk 分类: java 学习笔记 linux ubuntu 2015-07-06 17:49 74人阅读 评论(0) 收藏
- 2015 年度 Android 开发者必备的 5 个开源库
- 使用Visual Studio 2015开发Android 程序