ZOJ 1232 Adventure of Super Mario SPFA+DP-白红宇

ZOJ 1232 Adventure of Super Mario SPFA+DP

阅读量：5042 次

发布时间：2019-06-12

本文共 2609 字，大约阅读时间需要 8 分钟。

第一次做类似的题目，卡了好几天，最后看了爱酱的blog（http://blog.csdn.net/acm_cxlove/article/details/8679230）才会的，sad

题意大概是这样，给你一个图，求起点1到N的最短时间，你有一双鞋子，可以加速，一次性花费0的时间行走M单位的路程，但是鞋子只能用K次，并且鞋子使用的时候起点和终点都必须在节点上，不能在半路停下。并且使用的鞋子的时候不能穿过编号大于A的节点，在不使用鞋子的情况下行走单位路程花费单位时间。

dp[i][k]表示从起点到i这个点在使用了k次鞋子之后所要花费的最短时间。

显然有dp[i][k] = min{dp[j][k-1],dp[j][k]+d[j][i]},j != i

但是更新的顺序是个问题，容易产生后效性，一开始用dijkstra的时候就无法避免，但是用spfa的只要更新的时候顺便转移就好了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long LL;const int maxn = 105;const int maxm = maxn * maxn * 4;const int INF = INT_MAX / 4;int first[maxn],nxt[maxm],v[maxm],w[maxm],d[maxn][maxn];int A,B,M,L,K,N,dp[maxn][maxn],cnt;bool inq[maxn];void spfa_nocastle(int str,int *d) { memset(inq,0,sizeof(inq)); queue
                  
                    q; q.push(str); for(int i = 1;i <= N;i++) d[i] = INF; d[str] = 0; inq[str] = true; while(!q.empty()) { int x = q.front(); q.pop(); inq[x] = false; for(int i = first[x];i != 0;i = nxt[i]) { if(d[v[i]] > d[x] + w[i]) { d[v[i]] = d[x] + w[i]; if((v[i] <= A || v[i] == str) && !inq[v[i]]) { q.push(v[i]); inq[v[i]] = true; } } } }}void adde(int _u,int _v,int _w) { cnt++; v[cnt] = _v; w[cnt] = _w; nxt[cnt] = first[_u]; first[_u] = cnt;}void solve() { memset(inq,0,sizeof(inq)); queue
                   
                     q; q.push(1); inq[1] = true; for(int i = 0;i <= N;i++) { for(int j = 0;j <= K;j++) { dp[i][j] = INF; } } dp[1][0] = 0; while(!q.empty()) { int x = q.front(); q.pop(); inq[x] = false; for(int i = 0;i <= K;i++) { //不用鞋子 for(int j = first[x];j != 0;j = nxt[j]) { if(dp[v[j]][i] > dp[x][i] + w[j]) { dp[v[j]][i] = dp[x][i] + w[j]; if(!inq[v[j]]) { q.push(v[j]); inq[v[j]] = true; } } } if(i == 0) continue; //用鞋子 for(int j = 1;j <= N;j++) if(j != x && d[x][j] <= L) { if(dp[j][i] > dp[x][i - 1]) { dp[j][i] = dp[x][i - 1]; if(!inq[j]) { inq[j] = true; q.push(j); } } } } } int ans = INF; for(int i = 0;i <= K;i++) ans = min(ans,dp[N][i]); printf("%d\n",ans);}int main() { int T; scanf("%d",&T); for(int kase = 1;kase <= T;kase++) { memset(first,0,sizeof(first)); memset(nxt,0,sizeof(nxt)); scanf("%d%d%d%d%d",&A,&B,&M,&L,&K); cnt = 0; N = A + B; for(int i = 1;i <= M;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); adde(u,v,w); adde(v,u,w); } for(int i = 1;i <= N;i++) spfa_nocastle(i,d[i]); /* for(int i = 1;i <= N;i++) { for(int j = 1;j <= N;j++) { if(d[i][j] < INF) printf("%d ",d[i][j]); else printf("X "); } putchar('\n'); } */ solve(); } return 0;}

转载于:https://www.cnblogs.com/rolight/p/3856153.html

你可能感兴趣的文章