HDU5521 Meeting（[好题]最短路径）

本文主要是介绍HDU5521 Meeting（[好题]最短路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：一个人在1位置，另一个在n位置，俩人要见面，然后给出m个集合，告诉集合的城市之间的距离都是t。然后问最短路
解法：边太多，直接邻接表是存不下的，所以要换一个存储方式，存与边关联的点，与点关联的边。然后最短路用堆优化的dij算法。还有一点值得注意的是，一个集合只需要跑一次就可以了，因为是最短路跑过来的，集合里都已经是最短的了

#include<bits/stdc++.h>using namespace std;
#define LL long long
#define pb push_back
#define X first
#define Y second
#define cl(a,b) memset(a,b,sizeof(a))
typedef pair<int,int> P;
const int maxn=100005;
const LL inf=1<<27;
int n;
LL t[maxn];
vector<int> G[maxn],E[maxn];
void init(){for(int i=0;i<=n;i++){G[i].clear();E[i].clear();}
}
LL dis[maxn],dis2[maxn];
bool used[maxn];
void dij(int s){priority_queue<P,vector<P>,greater<P> > q;for(int i=1;i<=n;i++){dis[i]=inf;used[i]=false;}q.push(P(0,s));dis[s]=0;while(!q.empty()){P tt=q.top();q.pop();int u=tt.Y;if(dis[u]<tt.X)continue;for(int i=0;i<G[u].size();i++){if(used[G[u][i]])continue;///一个集合访问一次used[G[u][i]]=true;for(int j=0;j<E[G[u][i]].size();j++){int v=E[G[u][i]][j];int w=t[G[u][i]];if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push(P(dis[v],v));}}}}
}
int main(){int T,cas=1;scanf("%d",&T);while(T--){int m,num;scanf("%d%d",&n,&m);init();for(int i=1;i<=m;i++){scanf("%lld%d",&t[i],&num);for(int j=0;j<num;j++){int x;scanf("%d",&x);E[i].pb(x);G[x].pb(i);}}dij(n);for(int i=1;i<=n;i++){dis2[i]=dis[i];}dij(1);for(int i=1;i<=n;i++){dis[i]=max(dis[i],dis2[i]);}LL mi=inf;for(int i=1;i<=n;i++){if(mi>dis[i]){mi=dis[i];}}if(mi==inf){printf("Case #%d: Evil John\n",cas++);continue;}vector<int> ans;for(int i=1;i<=n;i++){if(dis[i]==mi){ans.pb(i);}}printf("Case #%d: %d\n",cas++,mi);int N=ans.size();for(int i=0;i<N;i++){printf("%d%c",ans[i],i==N-1?'\n':' ');}}return 0;
}