首页 > 代码库 > SPOJ FISHER + FPOLICE SPFA+背包

SPOJ FISHER + FPOLICE SPFA+背包

2024-07-08 04:14:04   224人阅读

当初第一次做的是FPLICE这个题，当时就觉得要用图论去搜索，但是当时陷入死思维就是 dp[][]两个维度都是点，这样就违背了题目的本意，题目给定了一个时间T，在不超过时间T的情况下求最小的消耗，这不就是背包嘛。。。即拿T做容量，在图上面 设置 dp[i][j]表示i点的时候 j时间的最小消耗。

这样走一遍spfa就可以了。也有人把这个叫做 分层图最短路。。。好高端的样子啊

FPOLICE

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#define N 110#define INF 1<<30using namespace std;int dp[N][260];int mat[N][N],risk[N][N];int inq[N][260];int n,T;struct node{    int i,t;};void bfs(){    queue <node> q;    q.push((node){0,0});    memset(inq,0,sizeof inq);    dp[0][0]=0;    while (!q.empty())    {        node cur=q.front();        inq[cur.i][cur.t]=0;        q.pop();        for (int i=0;i<n;i++)if (cur.i!=i){            if (cur.t+mat[cur.i][i]>T) continue;            int nt=cur.t+mat[cur.i][i];            if (dp[i][nt]>dp[cur.i][cur.t]+risk[cur.i][i]){                dp[i][nt]=dp[cur.i][cur.t]+risk[cur.i][i];                if (!inq[i][nt]){                    q.push((node){i,nt});                    inq[i][nt]=1;                }            }        }    }    int ansT=-1,ansR=INF;    for (int i=0;i<=T;i++){        if (dp[n-1][i]<ansR){            ansR=dp[n-1][i];            ansT=i;        }    }    if (ansT<0) puts("-1");    else printf("%d %d\n",ansR,ansT);}int main(){    int t;    scanf("%d",&t);    while (t--)    {        scanf("%d%d",&n,&T);        for (int i=0;i<n;i++){            for (int j=0;j<n;j++){                scanf("%d",&mat[i][j]);            }            for (int j=0;j<T+1;j++)                dp[i][j]=INF;        }        for (int i=0;i<n;i++)            for (int j=0;j<n;j++){                scanf("%d",&risk[i][j]);        }        bfs();    }    return 0;}

 

 

FISHER

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#define INF 1<<30using namespace std;struct node{    int x,T;};int dp[55][1010];int maT[55][55],maF[55][55];int n,t;int inq[55][1010];void spfa(){    memset(inq,0,sizeof inq);    queue <node> q;    q.push((node){0,0});    dp[0][0]=0;    while (!q.empty())    {        node u=q.front();q.pop();        inq[u.x][u.T]=0;        for (int v=0;v<n;v++){            if (v==u.x) continue;            int tot=u.T+maT[u.x][v];            if (tot>t) continue;            if (dp[v][tot]>dp[u.x][u.T]+maF[u.x][v]){                dp[v][tot]=dp[u.x][u.T]+maF[u.x][v];                if (!inq[v][tot]){                    q.push((node){v,tot});                    inq[v][tot]=1;                }            }        }    }}int main(){    while (scanf("%d%d",&n,&t) && n)    {        for (int i=0;i<n;i++)            for (int j=0;j<n;j++) scanf("%d",&maT[i][j]);        for (int i=0;i<n;i++)            for (int j=0;j<n;j++) scanf("%d",&maF[i][j]);        for (int i=0;i<=n;i++){            for (int j=0;j<=t+1;j++) dp[i][j]=INF;        }        spfa();        int ans=INF,loc=0;        for (int i=0;i<=t;i++){            if (ans>dp[n-1][i]){                ans=dp[n-1][i];                loc=i;            }        }        printf("%d %d\n",ans,loc);    }    return 0;}

 


联系
我们