题意：给出四边形的无向图，标号分别为0,1,2,3,然后从1出发最后回到1，路可以重复走多次，求使得走的路程>= k的最小值。
思路：怎么也不会想到是最短路，不过涨知识了。
下面思路转载自：http://blog.csdn.net/u013534123/article/details/76651821
题目要求是只有四个点，然后连边成正方形，问从2号点出发，再回到2号点且走过的总距离大于K的最短的路径是多少。对于这个，我们考虑如果存在一条合法路径，那么我再走2*w也一定是合法路径，其中w表示与2相连的某条边的长度。即回到2之后再出去再回来，这样的路径一定合法。那么，如果走了某条路径回到了2，然后总距离不够的话，我们只需要加上几个2*w使得最后结果大于等于K即可。 那么如何使这个结果最小呢？我们考虑设置一个数组d[x][p]表示从2出发最后到达x点且费用对2*w取模结果为p时的最小花费。这样子原本的一个点就可以拆成2*w个点，这样跑一遍dijkstra即可求出d数组。之后，对于每一个对2*w取模后的数值，我们都可以计算把它补到大于K且距离K最近的花费，再在这些花费中取一个最小的即可。那么，这样子考虑为什么可以包含全部的而且最优的解呢？因为我们最后补的是2*w或者它的倍数，然后我把对2*w取模后的所有取值的最小花费都计算了一次，这样子得出来的最小花费一定包含所有的情况，即2*w的所有剩余系都被包括了，所以可以保证正确性
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; typedef long long ll; typedef pair<ll,ll> P; ll k;ll a,b,c,d; ll m; ll dis[5][maxn]; struct Node{ll to, w;}; vector<Node>g[5]; void dijkstra() { for(ll i = 0; i < 5; i ++) for(ll j = 0; j <= m; j ++)dis[i][j] = 2LL * k; priority_queue<P,vector<P>,greater<P> >q; q.push(P(0,1)); while(!q.empty()) { ll t1 = q.top().first;ll u = q.top().second;q.pop(); if(t1 > dis[u][t1 % m])continue; for(ll i = 0; i < g[u].size(); i ++) { ll v = g[u][i].to;ll w = g[u][i].w;ll t = t1 + w; if(dis[v][t % m] > t)q.push(P(dis[v][t % m] = t,v)); } } } int main() { ll Tcase;scanf("%I64d",&Tcase); while(Tcase --) { for(ll i = 0; i < 5; i ++)g[i].clear(); scanf("%I64d%I64d%I64d%I64d%I64d",&k,&a,&b,&c,&d); g[1].push_back((Node){0,a});g[1].push_back((Node){2,b}); g[2].push_back((Node){1,b});g[2].push_back((Node){3,c}); g[3].push_back((Node){2,c});g[3].push_back((Node){0,d}); g[0].push_back((Node){1,a});g[0].push_back((Node){3,d}); m = min(a,b) * 2LL; dijkstra(); ll ans = k * 2; for(ll i = 0; i < m; i ++) { if(dis[1][i] >= k)ans = min(ans,dis[1][i]); else { ll t = k - dis[1][i]; ans = min(ans,dis[1][i] + ( (t % m ? 1 : 0) + t /m) * m); } } printf("%I64d\n",ans); } return 0; }
