题目链接
题意
存在一个含有4个点的图，给定1-2，2-3，3-4，4-1四条无向边的长度
d1,2,d2,3,d3,4,d4.1
和一个
K
值。问起点和终点均为2，可以不断在各个点之间不断往返，使得所经过的路程总长 S≥K 时的最小
S
为多少。
分析
来自题解的思路。设 w=2min(d2,1,d2,3) ，显然我们可以通过不断往返这一段路程使得总后的总路程满足要求。设往返前经过的路程为
d
，则这个推论可以表示为d a1×w≥K 。在
d≤K
时，等价于
dmodw+a2×w≥K
；而
d>K
的情况，实际可以直接判断是否为最小值。问题此时就转换成找到到达每个点特定取模值下的最短路问题，一次优先队列即可。详细可以参考代码理解。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 60600
#define eps 1e-7
#define lson rt<<1
#define rson rt<<1|1
#define LL long long
struct Node{
LL d;
int curidx,md;
Node(){}
Node(
int _curidx,
int _md,LL _d):curidx(_curidx),md(_md),d(_d){}
friend bool operator<(Node n1,Node n2){
return n1.d>n2.d;
}
};
int dis[
5][
5];
bool vis[
5][
60600];
int main(){
int T;
cin>>T;
memset(dis,-
1,
sizeof(dis));
while(T--){
LL K;
memset(vis,
0,
sizeof(vis));
scanf(
"%I64d %d %d %d %d",&K,&dis[
1][
2],&dis[
2][
3],&dis[
3][
4],&dis[
4][
1]);
dis[
2][
1]=dis[
1][
2];dis[
3][
2]=dis[
2][
3];dis[
1][
4]=dis[
4][
1];
dis[
4][
3]=dis[
3][
4];
int w=
2*min(dis[
1][
2],dis[
2][
3]);
priority_queue<Node> q;
q.push(Node(
2,
0,
0));
LL ans=(K+w-
1)/w*w;
while(!q.empty()){
Node tmp=q.top();
q.pop();
if(vis[tmp.curidx][tmp.md])
continue;
vis[tmp.curidx][tmp.md]=
1;
if(tmp.curidx==
2){
if(tmp.d>=K)
ans=min(tmp.d,ans);
else{
LL tot=K/w*w+tmp.md;
if(tot<K)
tot+=w;
ans=min(ans,tot);
}
}
for(
int i=
1;i<=
4;++i){
if(dis[tmp.curidx][i]!=-
1){
int mm=(tmp.md+dis[tmp.curidx][i])%w;
q.push(Node(i,mm,tmp.d+dis[tmp.curidx][i]));
}
}
}
printf(
"%I64d\n",ans);
}
}
