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.
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
思路: 非常显然的最短路。。。。一个月没写代码还能1A…感动
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
/* *********************************************** Author :111qqz Created Time :2016年07月06日 星期三 20时48分00秒 File Name :code/bzoj/1681.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E3+6; int n,m,cow,T; vector < pi > edge[N]; int d[N]; bool inq[N]; int posi[N]; vector <int>ans; void spfa( int s) { ms(inq,false); ms(d,0x3f); queue<int>q; q.push(s); d[s] = 0; inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; int siz = edge[u].size(); for ( int i = 0 ; i < siz ; i ++) { int v = edge[u][i].fst; if (d[v]>d[u]+edge[u][i].sec) { d[v] = d[u] + edge[u][i].sec; if (inq[v]) continue; inq[v] = true; q.push(v); } } } } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif scanf("%d%d%d%d",&n,&m,&cow,&T); for (int i = 1 ; i <= m ; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); edge[u].push_back(make_pair(v,w)); edge[v].push_back(make_pair(u,w)); } for ( int i = 1 ; i <= cow ; i++) scanf("%d",&posi[i]); spfa(1); for ( int i = 1 ; i <= cow ; i++) { if (d[posi[i]]<=T) ans.push_back(i); } printf("%d\n",ans.size()); for ( int i = 0 ; i < ans.size() ; i++) printf("%d\n",ans[i]); #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!