传送门
题意：
给出k,d12,d23,d34,d40分别表示要跑的总长度，1、2两点的距离，2、3两点的距离，3、4两点的距离，4、0两点的距离，从2出发再回到2，求超过k的最小累计长度。
思路：
1、从2出发回到2的最短路程 d = 2 * min(d12,d23)，然后再求出所有从2出发再回到2的对 d 取膜 为 1~d-1 的最短路，这个用dijkstra算法可以实现，最多进行 d次更新
#include<bits/stdc++.h> #define LL long long using namespace std; const LL INF = 2000000007; #define N 60005 struct edge { int v,nxt,dis; }e[105]; int head[105]; int tot; LL dp[4][N]; //dp[i][j] 表示到第i个点，余数为 j 的最短长度 typedef pair<LL,int>p; //分别存 长度 和 到的点 LL r; void add(int a,int b,int dis) { e[tot].v = b; e[tot].nxt = head[a]; e[tot].dis = dis; head[a] = tot++; } void dijkstra() { memset(dp,INF*INF,sizeof(dp)); dp[1][0] = 0; priority_queue<p,vector<p>,greater<p> >que; que.push( p(0LL,1) ); while(!que.empty()){ LL w = que.top().first; //w表示已经走的长度 int m = que.top().second; //m表示当前到的点 que.pop(); if(w>dp[m][w%r]) continue; for(int i=head[m];~i;i=e[i].nxt){ int v = e[i].v; if(w + e[i].dis >= dp[v][(w+e[i].dis)%r]) continue; dp[v][(w+e[i].dis)%r] = w + e[i].dis; que.push(p(w+e[i].dis,v)); } } } int main() { int t; scanf("%d",&t); while(t--){ memset(head,-1,sizeof(head)); tot = 0; LL k; int d1,d2,d3,d4; scanf("%lld%d%d%d%d",&k,&d1,&d2,&d3,&d4); r = 2 * min(d1,d2); add(0,1,d1); // 添加8条边 add(1,0,d1); add(1,2,d2); add(2,1,d2); add(2,3,d3); add(3,2,d3); add(3,0,d4); add(0,3,d4); dijkstra(); // 尝试求 d-1 个答案 LL ans = INF * INF; // 注意 k 有 2 * 10 ^ 18 所以 ans 要足够大 for(int i=0;i<r;i++){ if(dp[1][i]>k) ans = min(dp[1][i],ans); else{ ans = min(ans,dp[1][i] + (k - dp[1][i])/r*r + ((k - dp[1][i])%r>0) * r); } } printf("%lld\n",ans); } }
