博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
星际导航
阅读量:7286 次
发布时间:2019-06-30

本文共 2264 字,大约阅读时间需要 7 分钟。

星际导航

(nav.pas/c/cpp/in/out,1s,64MB)

题目描述

sideman做好了回到Gliese 星球的硬件准备,但是sideman的导航系统还没有完全设计好。为了方便起见,我们可以认为宇宙是一张有N 个顶点和M 条边的带权无向图,顶点表示各个星系,两个星系之间有边就表示两个星系之间可以直航,而边权则是航行的危险程度。

sideman 现在想把危险程度降到最小,具体地来说,就是对于若干个询问(A, B),sideman 想知道从顶点A 航行到顶点B 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学,你们要帮助sideman 返回家园,兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式

第一行包含两个正整数N 和M,表示点数和边数。

之后 M 行,每行三个整数A,B 和L,表示顶点A 和B 之间有一条边长为L 的边。顶点从1 开始标号。

下面一行包含一个正整数 Q,表示询问的数目。

之后 Q 行,每行两个整数A 和B,表示询问A 和B 之间最危险的边危险程度的可能最小值。

输出格式

对于每个询问, 在单独的一行内输出结果。如果两个顶点之间不可达, 输出impossible。

样例输入

4 5

1 2 5

1 3 2

2 3 11

2 4 6

3 4 4

3

2 3

1 4

1 2

样例输出

5

4

5

数据范围与约定

对于40% 的数据,满足N≤1000,M≤3000,Q≤1000。

对于 80% 的数据,满足N≤10000,M≤105,Q≤1000。

对于 100% 的数据,满足N≤105,M≤3×105,Q≤105,L≤109。数据不保证没有重边和自环。

   这种题的模型很常见,先最小生成树,再深搜处理出fat[],next[],d[]数组,分别表示生成树后每个节点的父亲,到父亲的路径权值,和此节点的深度,然后就可以一步一步先上搜,或者LCA更新答案。

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 using namespace std; 11 inline int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 int N,M,Q; 18 struct node{ 19 int x,y,w; 20 }e[300005]; 21 struct node1{ 22 int x,y; 23 }q[100005]; 24 int cmp(const node&a,const node&b){ 25 if(a.w
to[100005],cost[100005]; 34 inline void dfs(int,int); 35 inline int get_ans(int,int); 36 int d[100005]; 37 int fat[100005]; 38 int next[100005]; 39 int main(){ 40 //freopen("nav.in","r",stdin); 41 //freopen("nav.out","w",stdout); 42 N=read(); M=read(); 43 for(int i=1;i<=M;i++){ 44 int u,v,c; 45 u=read(); v=read(); c=read(); 46 e[i].x=u; e[i].y=v; e[i].w=c; 47 } 48 Q=read(); 49 for(int i=1;i<=Q;i++){ 50 int u,v; 51 u=read(); v=read(); 52 q[i].x=u; q[i].y=v; 53 } 54 sort(e+1,e+M+1,cmp); 55 for(int i=1;i<=N;i++) fa[i]=i; 56 for(int i=1;i<=M;i++){ 57 int u=e[i].x; int v=e[i].y; int c=e[i].w; 58 int fau=getfa(u); int fav=getfa(v); 59 if(fau!=fav){ 60 if(fau
d[y]) x=fat[x]; 98 else if(d[x]==d[y]) x=fat[x],y=fat[y]; 99 }100 while(u!=x) ans=max(ans,next[u]),u=fat[u];101 while(v!=y) ans=max(ans,next[v]),v=fat[v];102 return ans;103 }

 

转载于:https://www.cnblogs.com/CXCXCXC/p/4869218.html

你可能感兴趣的文章
关于visual assist x插件不能用的解决方案
查看>>
Linux iptables:规则组成
查看>>
HDU 4442 Physical Examination【水题】【思维题】
查看>>
NET 命令 常用方法!
查看>>
我的友情链接
查看>>
memcached
查看>>
谁搞死了你的软件?
查看>>
Promise 对象
查看>>
Windows快速添加IP地址
查看>>
AS3.0 事件流
查看>>
“将截断字符串或二进制数据。语句已终止……”问题的解决
查看>>
红苹果IP代理软件 v6.2
查看>>
Centos5.x & Centos6.x 使用mail命令发邮件以及如何伪造发件人
查看>>
JavaScript系列:ECMAScript原始类型
查看>>
centos反编译APK包
查看>>
CSS系列:CSS中盒子的浮动与定位
查看>>
windows 用户用户组迁移
查看>>
Linux系统扩充2
查看>>
linux新手的心得
查看>>
我的友情链接
查看>>