本文主要是介绍HDU 5521(最短路+建立虚点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5521
题目大意：一个农场被分成了n块，然后给m个集合，每个集合中的点互相到达的时间需要ti秒，一个人在第1块，一个人在第n块，问在第几块碰面花的时间最少，如果有多个块时间一样就按照从小到大输出
题目思路：由于直接建边的话边的数量极大，那么我们可以建一个虚点，每个集合对应一个虚点，集合中的每一个点都连在这个虚点上，出度是时间，入度是0，这样就可以既保证集合之间的权值，又能减少建边数量，然后直接跑迪杰斯特拉即可。
以下是代码：
#include<bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MAXN = 1e6+5;
const int MOD = 1e9+7;
struct Edge{int to,w,next;
}edge[MAXN<<1];
struct node{int v,c;bool operator <(const node &r)const{return c>r.c;}
}a;
int head[MAXN],tot,k;
void addedge(int u,int v,int w){edge[tot].to=v,edge[tot].w=w,edge[tot].next=head[u],head[u]=tot++;
}
bool vis[MAXN];
ll dist[MAXN],distx[MAXN],disty[MAXN];
vector<int>v;
void dij(int n,int s){memset(vis,false,sizeof(vis));memset(dist,0x3f,sizeof(dist));priority_queue<node>q;while(!q.empty())q.pop();dist[s]=0;a.v=s,a.c=0;q.push(a);while(!q.empty()){node temp=q.top();q.pop();int u=temp.v;if(vis[u])continue;vis[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to,w=edge[i].w;if(!vis[v]&&dist[v]>dist[u]+w){dist[v]=dist[u]+w;a.v=v,a.c=dist[v];q.push(a);}}}
}
int main()
{int t;scanf("%d",&t);rep(_,1,t){v.clear();int n,m,temp,k,x;scanf("%d%d",&n,&m);tot=0;memset(head,-1,sizeof(head));rep(i,1,m){scanf("%d%d",&temp,&k);rep(j,1,k){scanf("%d",&x);addedge(x,n+i,temp);addedge(n+i,x,0);}}dij(n+m,1);rep(i,1,n){distx[i]=dist[i];}dij(n+m,n);rep(i,1,n){disty[i]=dist[i];}ll ans=inf;rep(i,1,n){ll temp=max(distx[i],disty[i]);if(temp<ans){v.clear();v.push_back(i);ans=temp;}else if(temp==ans){v.push_back(i);}}int len=v.size();if(ans==inf){printf("Case #%d: Evil John\n",_);}else{printf("Case #%d: %lld\n",_,ans);rep(i,0,len-1){printf("%d%c",v[i],i==len-1?'\n':' ');}}}return 0;
}
这篇关于HDU 5521(最短路+建立虚点)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
