HDU 6071（同余最短路）题意：分析：代码：

86 阅读 0 评论 57 点赞

我是靠谱客的博主平常墨镜，这篇文章主要介绍HDU 6071（同余最短路）题意：分析：代码：，现在分享给大家，希望可以做个参考。

传送门：

题意：

给你四个点，相邻两个点之间有一条连边。现在问你从$2$号点走到$2$号点的至少为$K$的最短路的长度。

分析：

因为题目中的$K$比较大，因此一些乱搞的算法显然无法通过，而鉴于点数相对来说比较少，因此我们得研究一下这几个点所蕴涵的性质。

我们发现，对于$2$号结点，它有两条可行的边，我们设这两条边的距离分别为$d_{12}$以及$d_{23}$，其中最小的边为$w$，（即$w=min(d_{12},d_{23})$）。如果要从$2$号结点走回到$2$号结点，一个显然优的策略是我们至少要访问两次$w$边。即答案至少为$2*w$。

假设我们当前从$2$到$2$的最短路为$d_i$，则我们显然可以进行$t$次上述的操作，使得最终的答案满足$d_i+2*t*w ge K$。显然这是一个线性的方程组，参数为$d_i$以及$t$。而我们要知道$t$的大小，显然只需要知道$d_i %2w$的值即可。

因此，这个问题其实是一个线性同余的问题，因为最终的答案跟$d_i %2w$有关，我们可以设$dis[i][j]$，为从起点到$i$点，最短路径$%2w$余$j$的最短路长度。此时的状态数就直接被我们缩短为$2*w*4$个，因此此时我们直接可以用最短路算法去求解了。

最后我们只需要不断枚举$dis[2][j]$，判断求出最优的$t$以及$d_i$即可

时间复杂度：$mathcal{O}(wlogw)$

代码：

复制代码

#include <bits/stdc++.h>
#define maxn 10
using namespace std;
typedef long long ll;
typedef pair<ll,int>pll;
struct Node{
int to,next,cost;
}q[10];
const ll INF=0x3f3f3f3f3f3f3f3f;
int head[maxn],cnt=0;
ll dis[10][100005],d;
void add_edge(int from,int to,int cost){
q[cnt].next=head[from];
q[cnt].to=to;
q[cnt].cost=cost;
head[from]=cnt++;
}
void dijk(int x){
priority_queue<pll,vector<pll>,greater<pll> >que;
for(int i=0;i<=4;i++){
for(int j=0;j<=d;j++) dis[i][j]=INF;
}
dis[x][0]=0;
que.push(pll(0LL,x));
while(!que.empty()){
pll p=que.top();
que.pop();
x=p.second;
if(p.first>dis[x][p.first%d]) continue;
for(int i=head[x];i!=-1;i=q[i].next){
int to=q[i].to;
ll dd=q[i].cost+dis[x][p.first%d];
if(dis[to][dd%d]>dd){
dis[to][dd%d]=dd;
que.push(pll(dd,to));
}
}
}
}
int val[10];
int main()
{
int t;
scanf("%d",&t);
while(t--){
ll k;
scanf("%lld",&k);
memset(head,-1,sizeof(head));
cnt=0;
d=0;
for(int i=1;i<=4;i++){
scanf("%d",&val[i]);
d=max(1ll*val[i],d);
}
for(int i=1;i<=4;i++){
add_edge(i,i%4+1,val[i]);
add_edge(i%4+1,i,val[i]);
}
d*=2;
dijk(2);
ll minn=INF;
for(int i=0;i<=d;i++){
if(dis[2][i]==INF) continue;
if(dis[2][i]>=k){
minn=min(dis[2][i],minn);
}
else{
ll tmp=k-dis[2][i];
minn=min(minn,dis[2][i]+tmp/d*d+(i>0)*d);
}
}
printf("%lldn",minn);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define maxn 10
using namespace std;
typedef long long ll;
typedef pair<ll,int>pll;
struct Node{
int to,next,cost;
}q[10];
const ll INF=0x3f3f3f3f3f3f3f3f;
int head[maxn],cnt=0;
ll dis[10][100005],d;
void add_edge(int from,int to,int cost){
q[cnt].next=head[from];
q[cnt].to=to;
q[cnt].cost=cost;
head[from]=cnt++;
}
void dijk(int x){
priority_queue<pll,vector<pll>,greater<pll> >que;
for(int i=0;i<=4;i++){
for(int j=0;j<=d;j++) dis[i][j]=INF;
}
dis[x][0]=0;
que.push(pll(0LL,x));
while(!que.empty()){
pll p=que.top();
que.pop();
x=p.second;
if(p.first>dis[x][p.first%d]) continue;
for(int i=head[x];i!=-1;i=q[i].next){
int to=q[i].to;
ll dd=q[i].cost+dis[x][p.first%d];
if(dis[to][dd%d]>dd){
dis[to][dd%d]=dd;
que.push(pll(dd,to));
}
}
}
}
int val[10];
int main()
{
int t;
scanf("%d",&t);
while(t--){
ll k;
scanf("%lld",&k);
memset(head,-1,sizeof(head));
cnt=0;
d=0;
for(int i=1;i<=4;i++){
scanf("%d",&val[i]);
d=max(1ll*val[i],d);
}
for(int i=1;i<=4;i++){
add_edge(i,i%4+1,val[i]);
add_edge(i%4+1,i,val[i]);
}
d*=2;
dijk(2);
ll minn=INF;
for(int i=0;i<=d;i++){
if(dis[2][i]==INF) continue;
if(dis[2][i]>=k){
minn=min(dis[2][i],minn);
}
else{
ll tmp=k-dis[2][i];
minn=min(minn,dis[2][i]+tmp/d*d+(i>0)*d);
}
}
printf("%lldn",minn);
}
return 0;
}