HDU 5521 Meeting ( nlogn的dijkstra+拆点)
程序员文章站
2022-06-02 23:31:13
...
题目链接: HDU 5521
-
题意:
给定n和m,n表示n个点,m表示m个集合,给出每个集合包含的点的编号,第i个集合中各个点之间的距离为ti,问,A位于编号为1的点,B位于编号为n的点,若同时出发,最快需要多久能相遇(可停留在某点等待), 输出最小时间以及满足最小时间的相遇的点.
- 解法:
这道题目,很裸的dijkstra最短路,但是依据题目,若集合中两两建边,则边数可达到1e12,爆空间 ,所以采用拆点形式,给每个集合额外分配一个点,集合中所有的点直接与这个点相连,距离为ti, 则最终答案需要除以2.
- 图解:
- 未拆点前,集合中点的连接,(每条边都是双向)
- 1到2的距离 = 2到3的距离 = 3到1的距离 = ti
- 每个集合都得建立s^2条边, s表示集合的大小
-
拆点后
- 1到2的距离 = 2到3的距离 = 3到1的距离 = 2 * ti
- 每个集合都得建立2*s条边, s表示集合的大小
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define repp(i,a,b) for(int i=b; i>=a; --i)
#define mp make_pair
#define pb push_back
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int>vi;
const int maxn = 2e6+7;
struct edge{
int to,next;
ll w;
}e[maxn];
int fi[maxn], id=0;
void adde(int u, int v, int w){
//cout <<" pair => " << u<<" "<<v<<endl;
e[id].to = v;
e[id].w=w;
e[id].next = fi[u];
fi[u] = id++;
return ;
}
ll dis[2][maxn];
ll status;
struct cmp{
bool operator()( const int &a, const int &b){
return dis[status][a] > dis[status][b];
}
};
bool in[maxn];
void dij(int u, int s){
ms(in, false);
status = s;
priority_queue<int, vector<int>, cmp>que;
int i;
dis[status][u] = 0;
in[u] = 1;
que.push(u);
while(!que.empty()){
int v = que.top();
//cout << v <<endl;
in[v]=1;
que.pop();
for(i=fi[v]; ~i; i=e[i].next){
int to = e[i].to;
if(in[to]) continue;
if(dis[status][to] > dis[status][v]+e[i].w){
dis[status][to] = dis[status][v]+e[i].w;
que.push(to);
}
}
}
return ;
}
void init(){
ms(dis, inf), ms(fi, -1);
id = 0;
return ;
}
int ans[100005];
int main(){
// freopen("in.txt", "r", stdin);
int t, n, m, cas=0;
scanf("%d", &t);
while(t--){
init();
//cout << dis[0][0]<<endl;
ll w;
int len, v;
scanf("%d %d", &n, &m);
rep(i, 1, m){
scanf("%lld %d", &w, &len);
rep(j, 1, len){
scanf("%d", &v);
adde(i, v+m, w);
adde(v+m, i, w);
}
}
dij(1+m, 0);
ll d = inf;
int alen=0;
if(dis[0][n+m] != inf){
dij(n+m, 1);
rep(i, 1, n){
ll tmp = max(dis[0][i+m], dis[1][i+m]);
if(tmp < d){
d = tmp;
alen = 0;
ans[alen++]=i;
} else if(tmp == d){
ans[alen++]=i;
}
}
}
printf("Case #%d: ", ++cas);
if(d!=inf) {
printf("%d\n", d/2);
rep(i, 0, alen-2){
printf("%d ", ans[i]);
}
printf("%d\n", ans[alen-1]);
} else {
printf("Evil John\n");
}
}
return 0;
}
上一篇: 钟情“云计算”东华软件定增不成改发债
下一篇: 类与对象 - Java学习(二)