【BZOJ】1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明(spfa)
http://www.lydsy.com/JudgeOnline/problem.php?id=1681
太裸了。。
#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=505, Q=N*10, oo=~0u>>2;
int q[Q], front, tail, d[N], vis[N], ihead[N], cnt, n, x, y, m, ans;
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); read(y);
for1(i, 1, m) {
int u=getint(), v=getint(), w=getint();
add(u, v, w);
}
spfa();
CC(vis, 0);
for1(i, 1, x) {
int t=getint();
if(d[t]<=y) vis[i]=1, ++ans;
}
printf("%d\n", ans);
for1(i, 1, x) if(vis[i]) printf("%d\n", i);
return 0;
}
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.
Input
* Line 1: Four space-separated integers: F, P, C, and M * Lines 2..P+1: Three space-separated integers describing a path: F1, F2, and T. The path connects F1 and F2 and requires T seconds to traverse. * Lines P+2..P+C+1: One integer per line, the location of a cow. The first line gives the field number of cow 1, the second of cow 2, etc.
第1行输入四个整数F,只C,和M;
接下来P行每行三个整数描述一条路,起点终点和通过时间.
Output
* Line 1: A single integer N, the number of cows that could be guilty of the crime.
* Lines 2..N+1: A single cow number on each line that is one of the cows that could be guilty of the crime. The list must be in ascending order.
Sample Input
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7
Sample Output
1
2
3
4
HINT
Source
最新文章
- 移动端web开发——视口
- git 命令熟悉
- JS原型继承和类式继承
- 关于MAC
- centos 7.0最小化安装 查看yum 所有安装的软件包~
- Linux操作、hadoop和sh脚本小结
- Cityengine, 3ds MAX, FME
- .NET中Main函数使用小技巧
- leetcode 70
- highchart 导出图片, 显示空白
- iOS开发那些事-iOS应用本地化-文本信息本地化
- QQ空间g_tk加密算法PHP版
- Tornado的一个开源社区
- matlab读xls数据
- c#无限循环线程如何正确退出
- C#面试题记录
- 禁止微信内的H5页面上下拖动
- postgresql设置主键
- windows10禁用更新方法
- python中shelve模块的使用
热门文章
- Python list添加新元素
- OSI模型图文说明
- fopen /open,read/write和fread/fwrite区别
- Android中涉及到的焦点问题,focusable,clickable,enabled
- Solr控制覆盖或覆写索引开关
- java基础学习总结——GUI编程(二) 未学习
- linux配置java环境变量(详细) [转]
- cookie是什么? -- web
- TypeError: can&#39;t convert console.log(...) to primitive type
- unity, 相机空间 与 相机gameObject的局部空间