积攒已久的题目了,果断前两星期怎么做做不对,隔一段时间一做就对了。
题意:马里奥要求从结点1到a+b的最短路。前提是他有一种靴子能在任意距离小于l的结点之间飞(经过的路上必须为村庄,耗时为零),结点标号前a个为村庄,靴子只能用k次。
思路:这道题用floyd初始化+Dijkstra+dp就搞定了。刷了一段时间最短路,这样的做法已经做过几遍了。floyd初始化任意两个可飞到的结点的距离。Dijkstra处理最短路只要在dis数组后加一维状态就可。每次转移的时候分两部分,一部分是不用靴子就和正常的Dij一样,在一种是根据初始化的距离判断能否用靴子。
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <map> 11 #include <set> 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<int, int> pii; 20 typedef pair<int, S> 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<pii> 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<LEN; i++)Map[i].clear(); 42 for(int i=0; i<m; i++){ 43 scanf("%d%d%d", &x, &y, &v); 44 idis[x][y] = idis[y][x] = v; 45 Map[x].PB(MP(y, v)); 46 Map[y].PB(MP(x, v)); 47 } 48 } 49 50 void floyd() 51 { 52 for(int i=1; i<=n; i++)idis[i][i] = 0; 53 for(int k=1; k<=a; k++){ 54 for(int i=1; i<=n; i++){ 55 for(int j=1; j<=n; j++){ 56 idis[i][j] = min(idis[i][j], idis[i][k]+idis[k][j]); 57 } 58 } 59 } 60 } 61 62 void Dijkstra(int s) 63 { 64 priority_queue<pis, vector<pis>, 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<Map[nv].size(); i++){ 80 int x = Map[nv][i].first, y = Map[nv][i].second; 81 if(dis[x][nk] > 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 }