首页 > 代码库 > Gym 100169A 最短路
Gym 100169A 最短路
题意：不久后滑铁卢将会变得非常冷，但是幸运的是，很多建筑都被桥梁和隧道连接着，所以你不需要总是走在外面。但是现在建筑
物之间的连接是错综复杂的，很难知道某两个建筑物之间的最优路线，所以需要你写程序判断。
给出 n 个点，m 条无向边，以及 p 个查询，边分为两种，一种是暴露在外面的边，用 O 表示，另一种是在室内的边，用 I 表示；最优
路线遵循以下规则：
1）尽可能使得路径上暴露在外面的边权值和最少；
2）在满足第一个条件的情况下，尽可能使得总路程最少。
每次查询给出一个 起点 s 和终点 t，求 s -> t 的最优路线。若路线存在则输出路径上暴露在外面的边的总和，以及路径的总和；否则输出
“IMPOSSIBLE”。
分析：
最短路，此时最短路的定义有所改变；
1、outd[v] v到 s 的最短路，此路是暴露在外面的最短路；
2、sumd[v] v到 s 的最短路，此路是总路程最短；
有两种边：
1、I 在里面的边；
1、当 outd[e.to] > outd[u] 时，更新outd 和 sumd
2、当outd[e.to] ==outd[u] && sumd[e.to] > sumd[u] + e.dist;更新 sumd
2、O在外面的边；
1、尽管是外面的边，但还是可以选他，其条件是 outd[e.to] > outd[u] + e.dist;更新 outd,sumd
2、当 outd[e.to] == outd[u] + e.dist&&sum[e.t]>sumd[u] + e.dist；更新sumd
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 10005; 6 const int inf = 0x3f3f3f3f; 7 8 struct Edge { 9 int from,to,dist,s; 10 }; 11 12 struct HopeNode { 13 int u,outd,sum; 14 bool operator < (const HopeNode& rhs) const { 15 if(outd!=rhs.outd) 16 return outd > rhs.outd; 17 else return sum > rhs.sum; 18 } 19 }; 20 21 struct Dij { 22 int n,m; 23 vector<int> G[maxn]; 24 vector<Edge> edges; 25 int outd[maxn]; 26 int sum[maxn]; 27 bool vis[maxn]; 28 29 void init(int n) { 30 this->n = n; 31 for(int i=0;i<n;i++) 32 G[i].clear(); 33 edges.clear(); 34 } 35 36 void AddEdge(int from,int to,int dist,int s) { 37 edges.push_back((Edge){from,to,dist,s}); 38 m = edges.size(); 39 G[from].push_back(m-1); 40 } 41 42 void dijstra(int s) { 43 memset(vis,0,sizeof(vis)); 44 for(int i=0;i<n;i++) 45 { 46 outd[i] = inf; 47 sum[i] = inf; 48 } 49 50 outd[s] = 0; 51 sum[s] = 0; 52 53 priority_queue<HopeNode> q; 54 q.push((HopeNode){s,0,0}); 55 while(!q.empty()) { 56 HopeNode x = q.top(); 57 q.pop(); 58 59 int u = x.u; 60 if(vis[u]) 61 continue; 62 vis[u] = true; 63 for(int i=0;i<G[u].size();i++) { 64 Edge& e = edges[G[u][i]]; 65 if(e.s==1&&outd[e.to]>outd[u]) { 66 outd[e.to] = outd[u]; 67 sum[e.to] = sum[u] + e.dist; 68 q.push((HopeNode){e.to,outd[e.to],sum[e.to]}); 69 } 70 else if(e.s==1&&outd[e.to]==outd[u]&&sum[e.to]>sum[u]+e.dist) { 71 sum[e.to] = sum[u] + e.dist; 72 q.push((HopeNode){e.to,outd[e.to],sum[e.to]}); 73 } 74 else if(e.s==0&&outd[e.to]>outd[u]+e.dist) { 75 outd[e.to] = outd[u] + e.dist; 76 sum[e.to] = sum[u] + e.dist; 77 q.push((HopeNode){e.to,outd[e.to],sum[e.to]}); 78 } 79 else if(e.s==0&&outd[e.to]==outd[u]+e.dist&&sum[e.to]>sum[u]+e.dist) { 80 sum[e.to] = sum[u] + e.dist; 81 q.push((HopeNode){e.to,outd[e.to],sum[e.to]}); 82 } 83 } 84 } 85 } 86 }sol; 87 88 int main() 89 { 90 int n,m,q; 91 scanf("%d%d%d",&n,&m,&q); 92 sol.init(n); 93 for(int i=0;i<m;i++) { 94 int u,v,d; 95 char s[5]; 96 scanf("%d%d%d",&u,&v,&d); 97 scanf("%s",s); 98 if(s[0]==‘I‘) { 99 sol.AddEdge(u,v,d,1);100 sol.AddEdge(v,u,d,1);101 }102 else {103 sol.AddEdge(u,v,d,0);104 sol.AddEdge(v,u,d,0);105 }106 }107 108 while(q--) {109 int s,t;110 scanf("%d%d",&s,&t);111 sol.dijstra(s);112 printf("%d %d\n",sol.outd[t],sol.sum[t]);113 }114 115 return 0;116 }
Gym 100169A 最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。