Lazy Running

思路

還是利用同余的思想，假設存在一條長度為$k$的路，那么也一定存在一條$k+base$的路$base=2?min(d1,d2)$。

$dis[i][j]=x$表示的是，從$2?>i$點$x\equiv j(\mathrm{m}\mathrm{o}\mathrm{d}base)$的滿足條件的最小的$x$，所以我們只要求出所有的$dis[2][i]$，再通過同余的性質去得到我們的最短路的花費，對于$dis[2][i]>k$我們取$min(ans,dis[2][i])$，否則的話，我們取$min(ans,dis[2][i]+(k?dis[2][i]+mid?1)/mod?mod)$，之后我們就可以得到我們的正確解了

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 6e4 + 10;ll dis[5][N], k, d1, d2, d3, d4, mod;vector< pair< int, ll > > G[5];void Dijkstra() {priority_queue< pair< ll, int >, vector< pair< ll, int > >, greater< pair< ll, int > > > q;q.push(mp(0, 2));memset(dis, 0x3f, sizeof dis);dis[2][0] = 0;while(q.size()) {auto temp = q.top();q.pop();if(temp.first > dis[temp.second][temp.first % mod]) continue;for(auto i : G[temp.second]) {int to = i.first;ll w = i.second + temp.first;if(dis[to][w % mod] > w) {dis[to][w % mod] = w;q.push(mp(w, to));}}} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = read();while(t--) {k = read(), d1 = read(), d2 = read(), d3 = read(), d4 = read();mod = min(d1, d2) * 2;for(int i = 1; i <= 4; i++) G[i].clear();G[1].pb(mp(2, d1)), G[1].pb(mp(4, d4));G[2].pb(mp(3, d2)), G[2].pb(mp(1, d1));G[3].pb(mp(2, d2)), G[3].pb(mp(4, d3));G[4].pb(mp(3, d3)), G[4].pb(mp(1, d4));Dijkstra();ll ans = 0x3f3f3f3f3f3f3f3f;for(int i = 0; i < mod; i++) {if(k < dis[2][i]) ans = min(ans, dis[2][i]);else {ans = min(ans, dis[2][i] + (k - dis[2][i] + mod - 1) / mod * mod);}}printf("%lld\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的HDU 6071 Lazy Running（同余最短路的应用）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。