看懂题目意思，他的意思是求将所有的城市走一遍，危险度最小，并且给你两个s,t后让你求在走的时候，从s到t过程中危险度最大的值，并输出它，然后就是如何解决了，这个题目可以说简单，也可以说难通过思考可以知道s到t的路径进行遍历就是所谓的答案了所以通过LCA算法就可以解决问题，大家可以去看看LCA在图论上的算法
/*Author: 2486Memory: 0 KBTime: 2222 MSLanguage: C++11 4.8.2Result: AcceptedVJ RunId: 4236841Real RunId: 15859210*/#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>#include <vector>using namespace std;const int maxn=50000+5;const int maxm=100000+5;int N,M,m;int par[maxn],dist[maxn],depth[maxn],vis[maxn];struct edge {int u,v,cost;bool operator<(const edge &a)const {return cost<a.cost;}} es[maxm];struct ed {int to,cost;ed(int to,int cost):to(to),cost(cost) {}};vector<ed>G[maxn];void init(int c) {for(int i=0; i<maxn; i++) {par[i]=i;dist[i]=-1;if(c)G[i].clear();}memset(vis,false,sizeof(vis));}int find(int x) {return par[x]==x?x:par[x]=find(par[x]);}bool same(int x,int y) {return find(x)==find(y);}void unite(int x,int y) {x=find(x);y=find(y);par[x]=y;}int lca(int a, int b) { //a的深度<=b的深度int m1 = -1;while(depth[a] < depth[b]) { //将深度调到一样m1 = max(m1, dist[b]);b = par[b];}while(a != b) {//同时从节点走到祖先节点m1 = max(m1, dist[a]);m1 = max(m1, dist[b]);a = par[a], b = par[b];}return m1;}void kj() {sort(es,es+M);init(1);int cnt=0;/**********将组成最小生成树的边全都保存起来*************//**********大家都懂，这是Kruskal算法*************/for(int i=0; i<M; i++) {edge e=es[i];if(!same(e.v,e.u)) {unite(e.v,e.u);G[e.v].push_back(ed(e.u,e.cost));G[e.u].push_back(ed(e.v,e.cost));}}/***********************/dist[1]=0;depth[1]=0;queue<int>F;F.push(1);vis[1]=true;init(0);/*********这个是很重要的**************//*********以1号城市为根节点，然后就是开始遍历形成一棵树**************//***********大家可以想象一下，如果城市在一棵树的某个节点上************//***********那么什么才是从一个点到另一个点的路径呢？************//***********很简单，将他们从他们自己的节点向上递推到两个点的共同祖先就可以了************//***********中间经历的就是从一个点到另一个点的路径************//***********如此，就直接用队列处理一下即可************/while(!F.empty()) {int v=F.front();F.pop();for(int i=0; i<G[v].size(); i++) {ed e=G[v][i];if(vis[e.to])continue;vis[e.to]=true;par[e.to]=v;//他的父亲节点depth[e.to]=depth[v]+1;//他的深度dist[e.to]=e.cost;//从该节点到父亲节点的危险度F.push(e.to);}}/***********************/}int main() {int cases=1;//freopen("D://imput.txt","r",stdin);while(~scanf("%d%d",&N,&M)) {for(int i=0; i<M; i++) {scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);}if(cases!=1)printf("\n");//注意题目格式，需要换行kj();int s,t;scanf("%d",&m);while(m–) {scanf("%d%d",&s,&t);//读取命令if(depth[s]>depth[t])swap(s,t);printf("%d\n",lca(s,t));}cases++;}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
看天，看雪，安安静静，不言不语都是好风景。
