题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6071
题意：给你一个由四个节点组成的环，求从节点2出发，回到节点2的不小于k的最短路。
解法：见ICPCCAMP上面这个题：点击打开链接 有叉姐的强力回答。那个题和这个是一样的思路。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL inf = 1e16; const int maxn=5; int T,d1,d2,d3,d4,n,s; LL k,m; struct edge{ int v; LL w; }; vector<edge>g[maxn]; LL dp[4][70000]; void Dijstra(int s){ priority_queue<pair<LL,int>,vector<pair<LL,int> >, greater<pair<LL, int>> >q; for(int i=0; i<4; i++) for(int j=0; j<m; j++) dp[i][j]=inf; dp[s][0]=0; q.push(make_pair(0,s)); while(!q.empty()) { LL d=q.top().first; int u=q.top().second; q.pop(); if(d>dp[u][d%m]) continue; for(int i=0; i<g[u].size(); i++){ int v=g[u][i].v; LL dis = d+g[u][i].w; if(dp[v][dis%m]>dis){ dp[v][dis%m]=dis; q.push(make_pair(dis,v)); } } } } int main() { scanf("%d", &T); while(T--) { n=4; s=1; for(int i=0; i<4; i++) g[i].clear(); scanf("%lld%d%d%d%d",&k,&d1,&d2,&d3,&d4); g[0].push_back(edge{1,1LL*d1}); g[1].push_back(edge{0,1LL*d1}); g[1].push_back(edge{2,1LL*d2}); g[2].push_back(edge{1,1LL*d2}); g[2].push_back(edge{3,1LL*d3}); g[3].push_back(edge{2,1LL*d3}); g[3].push_back(edge{0,1LL*d4}); g[0].push_back(edge{3,1LL*d4}); m = min(1LL*d1, 1LL*d2) * 2; Dijstra(s); // puts("fuck"); LL ans = 1e19; for(int i=0; i<m; i++){ LL temp = k-dp[1][i]; if(temp<=0) ans=min(ans,dp[1][i]); else ans=min(ans,dp[1][i]+temp/m*m+(temp%m>0)*m); } printf("%lld\n", ans); } return 0; }
