首页 > 代码库 > ZOJ 1232 Adventure of Super Mario SPFA+DP

ZOJ 1232 Adventure of Super Mario SPFA+DP

2024-07-13 01:46:28   218人阅读

第一次做类似的题目，卡了好几天，最后看了爱酱的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 <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>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<int> 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<int> 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;}

　　


联系
我们