本文共 2189 字，大约阅读时间需要 7 分钟。
积攒已久的题目了，果断前两星期怎么做做不对，隔一段时间一做就对了。
题意：马里奥要求从结点1到a+b的最短路。前提是他有一种靴子能在任意距离小于l的结点之间飞（经过的路上必须为村庄，耗时为零），结点标号前a个为村庄，靴子只能用k次。
思路：这道题用floyd初始化+Dijkstra+dp就搞定了。刷了一段时间最短路，这样的做法已经做过几遍了。floyd初始化任意两个可飞到的结点的距离。Dijkstra处理最短路只要在dis数组后加一维状态就可。每次转移的时候分两部分，一部分是不用靴子就和正常的Dij一样，在一种是根据初始化的距离判断能否用靴子。
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define MP(a, b) make_pair(a, b) 13 #define PB(a) push_back(a) 14 15 using namespace std; 16 17 typedef long long ll; 18 typedef struct { int p, k;}S; 19 typedef pair pii; 20 typedef pair pis; 21 22 const int INF = 0x3f3f3f3f; 23 const double eps = 1E-6; 24 const int LEN = 110; 25 int a, b, m, l, k, n; 26 int idis[LEN][LEN], dis[LEN][LEN]; 27 vector Map[LEN]; 28 struct cmp 29 { 30 bool operator() (pis x, pis y){ return x.first > y.first;} 31 }; 32 33 inline S MS(int x, int y){S ret;ret.p = x,ret.k = y;return ret;} 34 35 void read() 36 { 37 int x, y ,v; 38 scanf("%d%d%d%d%d", &a, &b, &m, &l, &k); 39 n = a+b; 40 memset(idis, 0x3f, sizeof idis); 41 for(int i=0; i , cmp> q; 65 int vis[LEN][LEN] = { 0}; 66 for(int i=1; i<=n; i++){ 67 for(int j=0; j<=k; j++){ 68 dis[i][j] = INF; 69 } 70 } 71 dis[s][0] = 0; 72 q.push(MP(dis[s][0], MS(s,0))); 73 while(!q.empty()){ 74 pis nvex = q.top(); q.pop(); 75 S ts = nvex.second; 76 int nv = ts.p, nk = ts.k; 77 if(vis[nv][nk])continue; 78 vis[nv][nk] = 1; 79 for(int i=0; i dis[nv][nk] + y){ 82 dis[x][nk] = dis[nv][nk] + y; 83 q.push(MP(dis[x][nk], MS(x, nk))); 84 } 85 } 86 for(int i=1; i<=n; i++){ 87 int x = i; 88 if(idis[nv][x]<=l && dis[x][nk+1] > dis[nv][nk]){ 89 dis[x][nk+1] = dis[nv][nk]; 90 q.push(MP(dis[x][nk+1], MS(x, nk+1))); 91 } 92 } 93 } 94 } 95 96 int main() 97 { 98 // freopen("in.txt", "r", stdin); 99 100 int T;101 scanf("%d", &T);102 while(T--){103 read();104 floyd();105 Dijkstra(1);106 int ans = INF;107 for(int i=0; i<=k; i++)ans = min(ans, dis[n][i]);108 printf("%d\n", ans);109 }110 return 0;111 }
转载于:https://www.cnblogs.com/shu-xiaohao/p/3517963.html
