P5304
[GXOI/GZOI2019旅行者]
题目大意：求两个关键城市之间的最短距离
做法是正向反向跑两遍(dijkstra)，染色最后统计答案
考虑一条边((u,v,w))，找到能到(u)最近的关键城市(A)，和(v)能到的最近的关键城市(B)，那么这两个关键城市之间的距离就应该是(dis(A,u)+dis(u,v)+dis(v,B))，正向跑一遍(dijkstra)可以找到到(u)最近的关键城市的距离，反向跑一遍可以找到(v)到某个最近关键城市的距离，那么(ans)每次与这个(dis(A,u)+dis(u,v)+dis(v,B))更新就可以了。
注意的是：如果到(u)最近的关键城市和(v)到最近的关键城市是同一个城市的话，那么这样相当于是跑了一个环，那么这样不会更新答案。所以就需要染色，求最短路的时候如果这个点的距离是由上一个点的距离更新过来的，那么将这个点的色与上一个点的色染成一样的。所以后面在枚举每个((u,v,w))的时候就可以判断，如果(u)的颜色和(v)的颜色是一样的话，那么他们肯定是由同一个关键城市为起点更新来的，因为每个关键城市都被染成了不同的颜色，所以这样就可以判断是不是成环了。
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn = 1e5+6,inf = 1e9;
int T,n,m,k;
int city[maxn],f[maxn*5],t[maxn*5],l[maxn*5];
struct node{
int id;LL dis;
bool operator < (const node &C)const
{
return dis > C.dis;
}
};
struct qwq{
int cnt,head[maxn],to[maxn*5],next[maxn*5],color[maxn];
LL dis[maxn],len[maxn*5];
bool vis[maxn];
priority_queue <node> q;
void clear()
{
cnt = 0;
for(int i=0;i<=n;i++)
{
head[i] = 0;
vis[i] = 0;
}
}
inline void add(int u,int v,int w)
{
cnt ++;
to[cnt] = v;
len[cnt] = w;
next[cnt] = head[u];
head[u] = cnt;
}
void dijkstra()
{
for(int i=1;i<=n;i++) dis[i] = inf;
for(int i=1;i<=k;i++)
{
dis[city[i]] = 0;
color[city[i]] = city[i];
q.push((node){city[i],0});
}
while(!q.empty())
{
node M = q.top();q.pop();
int u = M.id;
if(vis[u]) continue;
vis[u] = 1;
for(int i=head[u];i;i=next[i])
{
int v = to[i];
if(dis[v] > dis[u] + len[i])
{
dis[v] = dis[u] + len[i];
color[v] = color[u];
q.push((node){v,dis[v]});
}
}
}
}
}Dij[2];
template <typename C>
inline void read(C &x)
{
x = 0;int f = 1; char c;
while(!isdigit(c = getchar()))
if(c == '-') f = -1;
while(isdigit(c))
x = (x << 3) + (x << 1) + (c & 15),c = getchar();
x *= f;
}
int main()
{
read(T);
while(T --)
{
LL ans = inf;
Dij[0].clear();Dij[1].clear();
read(n),read(m),read(k);
for(int i=1;i<=m;i++)
{
read(f[i]),read(t[i]),read(l[i]);
Dij[0].add(f[i],t[i],l[i]);
Dij[1].add(t[i],f[i],l[i]);
}
for(int i=1;i<=k;i++) read(city[i]);
Dij[0].dijkstra();Dij[1].dijkstra();
for(int i=1;i<=m;i++)
{
if(Dij[0].color[f[i]] != Dij[1].color[t[i]] && Dij[0].color[f[i]] && Dij[1].color[t[i]])
ans = min(ans,Dij[0].dis[f[i]]+l[i]+Dij[1].dis[t[i]]);
}
printf("%lld
",ans);
}
return 0;
}
我发现手写堆比STL快得多（9s->3s）
update : 2020/05/05
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
typedef long long LL;
using namespace std;
const int maxn = 1e5+6,inf = 1e9;
int T,n,m,k,tot;
int city[maxn],f[maxn*5],t[maxn*5],l[maxn*5];
struct node{
int id;LL dis;
}heap[maxn];
struct UMR{
int nx,sonx;
void push(node x)
{
tot ++;nx = tot;
heap[tot] = x;
while(1)
{
if(nx == 1) break;
if(heap[nx].dis < heap[nx>>1].dis)
{
swap(heap[nx],heap[nx>>1]);
nx >>= 1;
}
else break;
}
}
node pop()
{
heap[1] = heap[tot];
tot --;
nx = 1;
while(1)
{
if((nx << 1) > tot) break;
if(heap[nx<<1].dis < heap[(nx<<1)+1].dis)
sonx = (nx << 1);
else sonx = (nx << 1) + 1;
if(heap[sonx].dis < heap[nx].dis)
{
swap(heap[nx],heap[sonx]);
nx = sonx;
}
else break;
}
}
node top()
{
return heap[1];
}
bool empty()
{
return !tot ? true : false;
}
}q;
struct qwq{
int cnt,head[maxn],to[maxn*5],next[maxn*5],color[maxn];
LL dis[maxn],len[maxn*5];
bool vis[maxn];
void clear()
{
cnt = 0;
for(int i=0;i<=n;i++)
{
head[i] = 0;
vis[i] = 0;
}
}
inline void add(int u,int v,int w)
{
cnt ++;
to[cnt] = v;
len[cnt] = w;
next[cnt] = head[u];
head[u] = cnt;
}
void dijkstra()
{
for(int i=1;i<=n;i++) dis[i] = inf;
for(int i=1;i<=k;i++)
{
dis[city[i]] = 0;
color[city[i]] = city[i];
q.push((node){city[i],0});
}
while(!q.empty())
{
node M = q.top();q.pop();
int u = M.id;
if(vis[u]) continue;
vis[u] = 1;
for(int i=head[u];i;i=next[i])
{
int v = to[i];
if(dis[v] > dis[u] + len[i])
{
dis[v] = dis[u] + len[i];
color[v] = color[u];
q.push((node){v,dis[v]});
}
}
}
}
}Dij[2];
template <typename C>
inline void read(C &x)
{
x = 0;int f = 1; char c;
while(!isdigit(c = getchar()))
if(c == '-') f = -1;
while(isdigit(c))
x = (x << 3) + (x << 1) + (c & 15),c = getchar();
x *= f;
}
int main()
{
read(T);
while(T --)
{
LL ans = inf;
Dij[0].clear();Dij[1].clear();
read(n),read(m),read(k);
for(int i=1;i<=m;i++)
{
read(f[i]),read(t[i]),read(l[i]);
Dij[0].add(f[i],t[i],l[i]);
Dij[1].add(t[i],f[i],l[i]);
}
for(int i=1;i<=k;i++) read(city[i]);
Dij[0].dijkstra();Dij[1].dijkstra();
for(int i=1;i<=m;i++)
{
if(Dij[0].color[f[i]] != Dij[1].color[t[i]] && Dij[0].color[f[i]] && Dij[1].color[t[i]])
ans = min(ans,Dij[0].dis[f[i]]+l[i]+Dij[1].dis[t[i]]);
}
printf("%lld
",ans);
}
return 0;
}