Meeting
Time Limit:
12000/
6000 MS (Java/Others) Memory Limit:
262144/
262144 K (Java/Others)
Total Submission(s):
2602 Accepted Submission(s):
825
Problem Description
Bessie
and her friend Elsie decide
to have a meeting. However,
after Farmer John decorated his
fences they were separated
into different blocks. John's farm are divided
into n blocks labelled
from 1 to n.
Bessie lives
in the first block
while Elsie lives
in the n-th one. They have a map
of the farm
which shows
that it takes they ti minutes
to travel
from a block
in Ei
to another block
in Ei
where Ei (
1≤i≤m)
is a
set of blocks. They want
to know how soon they can meet each other
and which block should be chosen
to have
the meeting.
Input
The
first line
contains an
integer T (
1≤T≤
6),
the number of test cases. Then T test cases
follow.
The
first line
of input
contains n
and m.
2≤n≤
105. The following m lines describe
the sets Ei (
1≤i≤m). Each line will
contain two integers ti(
1≤ti≤
109)
and Si (Si>
0) firstly. Then Si
integer follows which are
the labels
of blocks
in Ei. It
is guaranteed
that ∑mi=
1Si≤
106.
Output
For each test case,
if they cannot have
the meeting,
then output
"Evil John" (
without quotes)
in one line.
Otherwise, output two lines. The
first line
contains an
integer,
the time it takes
for they
to meet.
The
second line
contains the numbers
of blocks
where they meet. If there are multiple
optional blocks, output all
of them
in ascending order.
Sample Input
2
5 4
1 3 1 2 3
2 2 3 4
10 2 1 5
3 3 3 4 5
3 1
1 2 1 2
Sample Output
Case
3 4
Case
这个题的提议是，有两个人，有
1-n块的地，一个人在第一块，一个人在第n块，
问你两个人面基,如果他们有机会碰到，问他在哪块地遇到(用时间最少，并且有多个答案，从小到大输出)
.
样例是给你m个集合，如何一个完全图呢。
这道题难在建图上。
多个集合有重复边怎么联系在一起。
其实只需要在每个集合加一个新的顶点，然后这个顶点与集合中的每一个点连接，
就这样建图，然后跑dijkstra就可以了。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<ctime>
#include<string>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#include<set>
#include<map>
#include<cstdio>
#include<limits.h>
#define MOD 1000000007
#define fir first
#define sec second
#define fin freopen("/home/ostreambaba/文档/input.txt", "r", stdin)
#define fout freopen("/home/ostreambaba/文档/output.txt", "w", stdout)
#define mes(x, m) memset(x, m, sizeof(x))
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define INF 1e9+7
#define inf 0x3f3f3f3f
#define Pi 4.0*atan(1.0)
#define lowbit(x) (x&(-x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max(a,b) a>b?a:b
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-12;
const int maxn = 1e5+10;
const int maxm = 1e6+10;
using namespace std;
inline int read(){
int x(0),f(1);
char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct edge{
int w,to,next;
};
edge g[maxn*2+maxm*2];
int tot;
int dis1[maxn*2+maxm*2];
int dis2[maxn*2+maxm*2];
int head[maxn+maxm];
bool vis[maxn*2+maxm*2];
void init(){
mes(head,-1);
tot=0;
}
void addEdge(int u,int v,int w){
g[tot].w=w;
g[tot].to=v;
g[tot].next=head[u];
head[u]=tot++;
}
void dijkstra(int s,int *dis,int p){
priority_queue<Pii,vector<Pii>,greater<Pii> > que;
fill(dis,dis+p+1,inf);
fill(vis,vis+p+1,false);
dis[s]=0;
vis[s]=true;
que.push(Pii(0,s));
while(!que.empty()){
Pii p=que.top();
que.pop();
int u=p.sec;
for(int i=head[u];~i;i=g[i].next){
int w=g[i].w;
int v=g[i].to;
if(vis[v]==false&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
vis[v]=true;
que.push(Pii(dis[v],v));
}
}
}
}
int main()
{
int Case=read();
for(int i=1;i<=Case;++i){
init();
int m,n;
int t,s,u;
n=read(),m=read();
for(int i=1;i<=m;++i){
t=read(),s=read();
while(s--){
u=read();
addEdge(u,n+i,t);
addEdge(n+i,u,t);
}
}
dijkstra(1,dis1,n+m);
dijkstra(n,dis2,n+m);
int res=inf;
for(int i=1;i<=n;++i){
res=min(res,max(dis1[i],dis2[i]));
}
vector<int> vec;
vec.clear();
for(int i=1;i<=n;++i){
if((max(dis1[i],dis2[i]))==res){
vec.push_back(i);
}
}
printf("Case #%d: ",i);
if(res!=inf){
printf("%d\n",res/2);
for(int i=0;i<(int)(vec.size()-1);++i){
printf("%d ",vec[i]);
}
printf("%d\n",vec.back());
}else{
printf("Evil John\n");
}
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-8226.html
