首页 > 代码库 > Codechef Bear and Clique Distances
Codechef Bear and Clique Distances
题目:https://www.codechef.com/problems/CLIQUED
描述:共有N个点,前1—K个点任意两点之间有一条无向边,边的权值为X,再任意给M条边(u,v,w)(不重复),求任意一点到其余各点的最短路。
分析:
1.最短路算法(usual Dijkstra)+一点小变形(a little twist)
2.trick:设置一个变量upd=1;因为前K个点之前两两是连通的,所以当第一次到前K个点中任一点(假设为u)时,就可以更新得到前K个点的距离(除了u)d[i](i<=k)为d[u]+X。
即:1-K中任意一点作为中间点更新1-K之间其他点的距离只用更新一次,因为最短路算法中每次队列取出来的点都是当前剩下点中距离源点最近的点,还有就是下次再更新到1-K点中的点时不用再继续更新与该点相连的1-K点的距离了
3.复杂度:O((m+k)log(V))
4.边的权值范围到达1e9,前面WA了几次,因为初始化inf=1e9+10;值太小了,有很多边,假如所有边大小都是1e9,则路径长度加起来远远大于初始化位1e9+10的inf。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 #include<map> 10 11 using namespace std; 12 #define maxn 100000+10 13 #define inf 1e15+10 //该题中inf定义为1e9+10 太小,导致出错 14 #define ll long long 15 16 struct Edge{ 17 ll u,v,w; 18 Edge(ll u=0,ll v=0,ll w=0):u(u),v(v),w(w){} 19 }; 20 21 struct Node{ 22 ll d,u; 23 bool operator<(const Node& rhs)const{ 24 return d>rhs.d; 25 } 26 }; 27 28 Edge edges[maxn]; 29 vector<ll>G[maxn]; 30 ll N,M,X,K,S; 31 bool vis[maxn]; 32 ll d[maxn]; 33 34 void Dijkstra() 35 { 36 bool flag=false; 37 priority_queue<Node>Q; 38 39 for(int i=1;i<=N;i++) d[i]=inf; 40 //memset(d,127,sizeof(d)); 41 memset(vis,0,sizeof(vis)); 42 43 d[S]=0; 44 Q.push(Node{0,S}); 45 while(!Q.empty()) 46 { 47 Node x=Q.top();Q.pop(); 48 //cout<<x.d<<" "<<x.u<<endl; 49 ll u=x.u; 50 if(vis[u]) continue; 51 vis[u]=true; 52 if(u<=K && !flag) 53 { 54 flag=true; 55 for(int i=1;i<=K;i++) 56 { 57 if(i!=u && d[i]>d[u]+X) 58 { 59 d[i]=d[u]+X; 60 Q.push(Node{d[i],i}); 61 } 62 } 63 } 64 //cout<<G[u].size()<<endl; 65 for(int i=0;i<G[u].size();i++) 66 { 67 ll id=G[u][i]; 68 //cout<<id<<endl; 69 ll x1=edges[id].u,x2=edges[id].v,x3=edges[id].w; 70 ll v=u==x1?x2:x1; 71 if(d[v]>d[u]+x3) 72 { 73 d[v]=d[u]+x3; 74 Q.push(Node{d[v],v}); 75 } 76 } 77 78 } 79 80 } 81 82 int main() 83 { 84 int t; 85 scanf("%d",&t); 86 while(t--) 87 { 88 89 scanf("%lld%lld%lld%lld%lld",&N,&K,&X,&M,&S); 90 for(int i=1;i<=N;i++) G[i].clear(); 91 for(int i=0;i<M;i++) 92 { 93 ll a,b,c; 94 scanf("%lld%lld%lld",&a,&b,&c); 95 edges[i]=Edge(a,b,c); 96 G[a].push_back(i); 97 G[b].push_back(i); 98 } 99 //for(int i=1;i<=N;i++) cout<<G[i].size()<<" "; 100 //cout<<endl; 101 Dijkstra(); 102 103 for(int i=1;i<=N;i++) 104 printf("%lld%c",d[i],i==N?‘\n‘:‘ ‘); 105 } 106 return 0; 107 }
Codechef Bear and Clique Distances
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。