Gym 100169A 最短路-LMLPHP

题意:不久后滑铁卢将会变得非常冷,但是幸运的是,很多建筑都被桥梁和隧道连接着,所以你不需要总是走在外面。但是现在建筑

物之间的连接是错综复杂的,很难知道某两个建筑物之间的最优路线,所以需要你写程序判断。

给出 n 个点,m 条无向边,以及 p 个查询,边分为两种,一种是暴露在外面的边,用 O 表示,另一种是在室内的边,用 I 表示;最优

路线遵循以下规则:

1)尽可能使得路径上暴露在外面的边权值和最少;

2)在满足第一个条件的情况下,尽可能使得总路程最少。

每次查询给出一个 起点 s 和终点 t,求  s -> t 的最优路线。若路线存在则输出路径上暴露在外面的边的总和,以及路径的总和;否则输出

“IMPOSSIBLE”。

分析:

最短路,此时最短路的定义有所改变;

1、outd[v] v到 s 的最短路,此路是暴露在外面的最短路;

2、sumd[v] v到 s 的最短路,此路是总路程最短;

有两种边:

Gym 100169A 最短路-LMLPHP

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

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;
const int inf = 0x3f3f3f3f; struct Edge {
int from,to,dist,s;
}; struct HopeNode {
int u,outd,sum;
bool operator < (const HopeNode& rhs) const {
if(outd!=rhs.outd)
return outd > rhs.outd;
else return sum > rhs.sum;
}
}; struct Dij {
int n,m;
vector<int> G[maxn];
vector<Edge> edges;
int outd[maxn];
int sum[maxn];
bool vis[maxn]; void init(int n) {
this->n = n;
for(int i=;i<n;i++)
G[i].clear();
edges.clear();
} void AddEdge(int from,int to,int dist,int s) {
edges.push_back((Edge){from,to,dist,s});
m = edges.size();
G[from].push_back(m-);
} void dijstra(int s) {
memset(vis,,sizeof(vis));
for(int i=;i<n;i++)
{
outd[i] = inf;
sum[i] = inf;
} outd[s] = ;
sum[s] = ; priority_queue<HopeNode> q;
q.push((HopeNode){s,,});
while(!q.empty()) {
HopeNode x = q.top();
q.pop(); int u = x.u;
if(vis[u])
continue;
vis[u] = true;
for(int i=;i<G[u].size();i++) {
Edge& e = edges[G[u][i]];
if(e.s==&&outd[e.to]>outd[u]) {
outd[e.to] = outd[u];
sum[e.to] = sum[u] + e.dist;
q.push((HopeNode){e.to,outd[e.to],sum[e.to]});
}
else if(e.s==&&outd[e.to]==outd[u]&&sum[e.to]>sum[u]+e.dist) {
sum[e.to] = sum[u] + e.dist;
q.push((HopeNode){e.to,outd[e.to],sum[e.to]});
}
else if(e.s==&&outd[e.to]>outd[u]+e.dist) {
outd[e.to] = outd[u] + e.dist;
sum[e.to] = sum[u] + e.dist;
q.push((HopeNode){e.to,outd[e.to],sum[e.to]});
}
else if(e.s==&&outd[e.to]==outd[u]+e.dist&&sum[e.to]>sum[u]+e.dist) {
sum[e.to] = sum[u] + e.dist;
q.push((HopeNode){e.to,outd[e.to],sum[e.to]});
}
}
}
}
}sol; int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
sol.init(n);
for(int i=;i<m;i++) {
int u,v,d;
char s[];
scanf("%d%d%d",&u,&v,&d);
scanf("%s",s);
if(s[]=='I') {
sol.AddEdge(u,v,d,);
sol.AddEdge(v,u,d,);
}
else {
sol.AddEdge(u,v,d,);
sol.AddEdge(v,u,d,);
}
} while(q--) {
int s,t;
scanf("%d%d",&s,&t);
sol.dijstra(s);
printf("%d %d\n",sol.outd[t],sol.sum[t]);
} return ;
}

  

05-14 08:35