HDU 5521 Meeting

时间:2023-03-08 16:57:45
HDU 5521 Meeting

2015 ACM / ICPC 沈阳站现场赛 M题

最短路

设置N+M个节点,前N个节点是Block,后M个节点是Set,每一组Set中的点向该Set连边,从1和n开始分别求最短路。注意爆int。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; const long long INF=1e16;
const int maxn=+;
const int maxm=+;
long long dis1[maxn],dis2[maxn],val[maxn];
bool flag1[maxn],flag2[maxn];
vector<int>G[maxn];
vector<int>Ans;
struct Edge
{
int from;
int to;
}e[maxm];
int T,n,m,tot; void init()
{
memset(val,,sizeof val);
memset(flag1,,sizeof flag1);
for(int i=;i<maxn;i++) dis1[i]=INF;
memset(flag2,,sizeof flag2);
for(int i=;i<maxn;i++) dis2[i]=INF;
for(int i=;i<maxn;i++) G[i].clear();
Ans.clear();
tot=;
} void AddEdge(int x,int y)
{
tot++;
e[tot].from=x;
e[tot].to=y;
G[x].push_back(tot); tot++;
e[tot].from=y;
e[tot].to=x;
G[y].push_back(tot);
} void spfa1()
{
queue<int>Q;
Q.push(); flag1[]=;dis1[]=;
while(!Q.empty())
{
int h=Q.front(); Q.pop(); flag1[h]=;
for(int i=;i<G[h].size();i++)
{
int id=G[h][i];
if(dis1[h]+val[e[id].to]<dis1[e[id].to])
{
dis1[e[id].to]=dis1[h]+val[e[id].to];
if(flag1[e[id].to]==)
{
flag1[e[id].to]=;
Q.push(e[id].to);
}
}
}
}
} void spfa2()
{
queue<int>Q;
Q.push(n); flag2[n]=;dis2[n]=;
while(!Q.empty())
{
int h=Q.front(); Q.pop(); flag2[h]=;
for(int i=;i<G[h].size();i++)
{
int id=G[h][i];
if(dis2[h]+val[e[id].to]<dis2[e[id].to])
{
dis2[e[id].to]=dis2[h]+val[e[id].to];
if(flag2[e[id].to]==)
{
flag2[e[id].to]=;
Q.push(e[id].to);
}
}
}
}
} int main()
{
scanf("%d",&T);
for(int Case=;Case<=T;Case++)
{
init();
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int s,x; long long t;
scanf("%lld%d",&t,&s);
val[n+i]=t;
for(int j=;j<=s;j++)
{
scanf("%d",&x);
AddEdge(x,n+i);
}
} spfa1();
spfa2(); long long ans=INF;
for(int i=;i<=n;i++)
{
if(dis1[i]==INF||dis2[i]==INF) continue;
if(max(dis1[i],dis2[i])<ans) ans=max(dis1[i],dis2[i]);
}
printf("Case #%d: ",Case);
if(ans==INF) printf("Evil John\n");
else
{
printf("%lld\n",ans);
for(int i=;i<=n;i++)
{
if(dis1[i]==INF||dis2[i]==INF) continue;
if(max(dis1[i],dis2[i])==ans) Ans.push_back(i);
}
for(int i=;i<Ans.size();i++)
{
printf("%d",Ans[i]);
if(i<Ans.size()-) printf(" ");
else printf("\n");
}
}
} return ;
}