岳阳手机网站建设,商场设计理念,社区网站模版,建网站服务公司Lazy Running
思路
还是利用同余的思想#xff0c;假设存在一条长度为kkk的路#xff0c;那么也一定存在一条kbasek basekbase的路base2∗min(d1,d2)base 2 * min(d1, d2)base2∗min(d1,d2)。 dis[i][j]xdis[i][j] xdis[i][j]x表示的是#xff0c;从2−i2 - i2…Lazy Running
思路
还是利用同余的思想假设存在一条长度为kkk的路那么也一定存在一条kbasek basekbase的路base2∗min(d1,d2)base 2 * min(d1, d2)base2∗min(d1,d2)。
dis[i][j]xdis[i][j] xdis[i][j]x表示的是从2−i2 - i2−i点x≡j(modbase)x \equiv j \pmod {base}x≡j(modbase)的满足条件的最小的xxx所以我们只要求出所有的dis[2][i]dis[2][i]dis[2][i]再通过同余的性质去得到我们的最短路的花费对于dis[2][i]kdis[2][i] kdis[2][i]k我们取min(ans,dis[2][i])min(ans, dis[2][i])min(ans,dis[2][i])否则的话我们取min(ans,dis[2][i](k−dis[2][i]mid−1)/mod∗mod)min(ans, dis[2][i] (k - dis[2][i] mid - 1) / mod * mod)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 \nusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, 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;
}
