英文wordpress建站,六安网站建设找哪家,深圳市住房建设局官方网站,网站后台用什么语言Meeting HDU - 5521
题意#xff1a;
一共有n个点#xff0c;有m个块#xff0c;每个块内有Si个点#xff0c;块内点彼此到达费用为wi#xff0c;两个人分别位于1和n号块#xff0c;两者同时出发问最短时间遇到是多少#xff1f;在哪些地方可以遇到#xff1f; ΣSi
一共有n个点有m个块每个块内有Si个点块内点彼此到达费用为wi两个人分别位于1和n号块两者同时出发问最短时间遇到是多少在哪些地方可以遇到 ΣSi106
题解
题意很明确我们需要先建边然后从点1开始跑最短路得到dis[i]再从点n跑最短路得到dist[i] dis[i]表示第1个点到第i个点的最短距离 dist[i]表示第n个点到第i个点的最短距离 答案就是minn minmaxdis[i],dist[i],minn 因为两者同时出发所以时间取长者然后找最短时间所以取min 题目难度在于ΣSi106如果你按照块内所有点两两建边那复杂度肯定暴力。考虑极端情况所有点在一个块内那怎么解决我们可以在块外建议一个新点x让块内所有点与其相连边权不变这样任意两个点都可以通过这个x中间点实现连接这样就巧妙建边(会网络流的应该好理解相当于一个人造源点) 建议不要用ios::sync_with_stdio(0);玄学错误导致我wa了八次
代码
#include bits/stdc.h
using namespace std;
#define asd cout SB endl;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
const int maxn1e69;
struct node{int v;int c;node(int v0,int c0):v(v),c(c){}bool operator(const node r)const{return cr.c;}
};
struct cmp{int x;cmp(int x0):x(x){}bool operator(const cmp r)const{return xr.x;}
};
struct Edge{int v,cost;Edge(int _v0,int _cost0):v(_v),cost(_cost){}
};
vectorEdgeE[maxn];
bool vis[maxn];
int dist[maxn];
int dis[maxn];
void dij(int n,int start){memset(vis,0,sizeof(vis));for(int i1;in;i)dist[i]INF;priority_queuenodeq;while(!q.empty())q.pop();dist[start]0;q.push(node(start,0));node tmp;while(!q.empty()){tmpq.top();q.pop();int utmp.v;if(vis[u])continue;vis[u]1;for(int i0;iE[u].size();i){int vE[tmp.v][i].v;int costE[u][i].cost;if(!vis[v]dist[v]dist[u]cost){dist[v]dist[u]cost;q.push(node(v,dist[v]));}}}
}
int main(){ios::sync_with_stdio(0);int t;cint;int cas0;while(t--){memset(E,0,sizeof(E));int n,m;cinnm;
// for(int i1;in;i)dis[i]INF;int tot0;for(int i1;im;i){int w;cinw;int S;cinS;for(int j1;jS;j){int x;cinx;// printf(u%d v%d w%d\n,ni,x,w);E[ni].push_back(Edge(x,w));E[x].push_back(Edge(ni,w));}}
// for(int in1;inm;i){
// for(int ji1;jnm;j){
// printf(u%d v%d w%d\n,i,j,0);
// E[i].push_back(Edge(j,0));
// E[j].push_back(Edge(i,0));
// }
// }dij(nm,1);for(int i1;in;i)dis[i]dist[i];dij(nm,n);int minnINF;for(int i1;in;i)minnmin(minn,max(dis[i],dist[i]));if(minnINF){printf(Case #%d: Evil John\n,cas);continue;}priority_queuecmpq;for(int i1;in;i){if(max(dis[i],dist[i])minn){q.push(i);}}bool f0;printf(Case #%d: %d\n,cas,minn/2);while(!q.empty()){if(f0)printf(%d,q.top().x);else printf( %d,q.top().x);q.pop();f1;}printf(\n);}return 0;
}
/*
2
5 4
1 3 1 2 3
2 2 3 4
3 2 1 5
3 3 3 4 5
3 1
1 2 1 2
*/
