题目
题目链接:https://codeforces.com/problemset/problem/1473/E
一张 \(n\) 个点 \(m\) 条边的无向图,定义一条路径长度为其边权之和减去边权最大值再加上边权最小值。求 \(1\) 到所有点的最短路。
\(n,m\leq 2\times 10^5\)。
思路
等价于最大边权不用计算,最小边权乘二的最短路。
容易发现,我们其实不用强制最大值或者最小值,如果我们能保证最终路径中只有一条不被计算,一条长度乘二,那么一定会选到最大值和最小值才会最优。
所以直接上分层图最短路即可。分为三层,第一层到第二层连边权为 \(0\) 的边,第二层到第三层连边权两倍的边。正反都要跑一遍。
注意如果有 \(1\to i\) 的边,那么需要特判一下 \(i\) 的最短路可以是这条边的边长。
时间复杂度 \(O((n+m)\log n)\)。
代码
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
const int N=600010,M=2000010;
int n,m,tot,head[N],U[N],V[N],D[N];
ll dis[N],ans[N];
bool vis[N];
struct edge
{
int next,to,dis;
}e[M];
void add(int from,int to,int dis)
{
e[++tot]=(edge){head[from],to,dis};
head[from]=tot;
}
void dij(int S)
{
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
priority_queue<pair<ll,int> > q;
q.push(mp(0,S)); dis[S]=0;
while (q.size())
{
int u=q.top().second; q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
q.push(mp(-dis[v],v));
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(ans,0x3f3f3f3f,sizeof(ans));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&U[i],&V[i],&D[i]);
int x=U[i],y=V[i],z=D[i];
add(x,y,z); add(y,x,z);
add(x+n,y+n,z); add(y+n,x+n,z);
add(x+n*2,y+n*2,z); add(y+n*2,x+n*2,z);
add(x,y+n,0); add(y,x+n,0);
add(x+n,y+n*2,z*2); add(y+n,x+n*2,z*2);
if (x==1) ans[y]=min(ans[y],1LL*z);
if (y==1) ans[x]=min(ans[x],1LL*z);
}
dij(1);
for (int i=2;i<=n;i++)
ans[i]=min(ans[i],dis[n*2+i]);
memset(head,-1,sizeof(head));
tot=0;
for (int i=1;i<=m;i++)
{
int x=U[i],y=V[i],z=D[i];
add(x,y,z); add(y,x,z);
add(x+n,y+n,z); add(y+n,x+n,z);
add(x+n*2,y+n*2,z); add(y+n*2,x+n*2,z);
add(x,y+n,z*2); add(y,x+n,z*2);
add(x+n,y+2*n,0); add(y+n,x+n*2,0);
}
dij(1);
for (int i=2;i<=n;i++)
printf("%lld ",min(ans[i],dis[n*2+i]));
return 0;
}