题目
题目链接:https://codeforces.com/contest/1528/problem/D
一张 \(n\) 个点 \(m\) 条边的有向图,第 \(i\) 条边为 \((u_i,v_i,d_i)\)。每一秒所有边到达的点的编号都会加一,也就是第 \(c\) 秒时,第 \(i\) 条边会变为 \((u_i,(v_i+c)\bmod n,d_i)\)。
求全源最短路。注意可以在任意点停留任意时间。
\(n\leq 600;m\leq n^2\),保证每一个点都有出边。
思路
显然难点就在于可以在可以停留,否则直接跑 dijkstra 即可。
考虑在原图中增加 \(n\) 条边,其中第 \(i\) 条为 \((i,(i+1)\bmod n,1)\),这样有一个非常妙的地方:假设我们要在 \(u\) 等 \(c\) 秒,然后去到 \(v\),那么等价于这一个时刻直接从 \(u\) 去到 \(v-c\),然后不断走新的边 \(c\) 次到达 \(u\)。
除了第一步不能走新建的边之外,其他时刻都可以任意走,因为走一次新建的边等价于在上一次走原图的时刻多等一秒。
那么直接枚举所有源点,然后新建一个点 \(S\) 把这一个点除了新加的路径以外所有路径 copy 过去,然后正常跑 dijkstra 即可。
时间复杂度 \(O(n^3)\)。注意因为边数是 \(O(n^2)\) 的,所以不要采用堆优化 dijkstra。否则将会退化成 \(O(nm\log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=610,M=400010;
int n,m,tot,tot1,head[N];
bool vis[N];
ll dis[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;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x+1,y+1,z);
}
tot1=tot;
for (int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
head[n+1]=-1; dis[n+1]=0; tot=tot1;
for (int j=head[i];~j;j=e[j].next)
add(n+1,e[j].to,e[j].dis);
for (int j=1;j<=n;j++)
{
int k=0;
for (int l=1;l<=n+1;l++)
if (!vis[l] && (!k || dis[l]<dis[k])) k=l;
vis[k]=1;
for (int l=head[k];~l;l=e[l].next)
{
int v=(e[l].to+dis[k]-1)%n+1;
dis[v]=min(dis[v],dis[k]+e[l].dis);
}
if (k<=n) dis[k%n+1]=min(dis[k%n+1],dis[k]+1);
}
dis[i]=0;
for (int j=1;j<=n;j++) cout<<dis[j]<<' ';
printf("\n");
}
return 0;
}