|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #define ll long long #define mod 100003 #define E 1000010 using namespace std;//丑陋的头文件终于结束 inline ll read(){ ll res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; }//丑陋的读优 inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } }//丑陋的输优 //queue<ll> q; //set<ll> s; //priority_queue<ll> q1; //priority_queue<ll,vector<ll>,greater<ll> > q2; //list<ll> l; //stack<ll> s; int n,k,a,b,c; int has[110][110];//有木有油箱 int dis[110][110][15];//当前状态的最小花费 struct node{ int x,y,z;//状态记录，分别为x坐标、y坐标、还有多少油 }; struct queue{ node val[10000000];int s,t; void clean(){ memset(val,0,sizeof(val)); s=0;t=0;//清空（貌似没有用到过） } void push(node tmp){ ++t; t%=10000000; val[t]=tmp;//加入队尾 } inline node front(){ return val[(s+1)%10000000];//循环队列，get队首 } void pop(){ s++;//弹出 s%=10000000;//循环队列 } bool empty(){//判断是否为空 if(s>=t) return 1; else return 0; } }q;//队列 node make(int x,int y,int z){ node pp;pp.x=x;pp.y=y;pp.z=z; return pp; }//方便快捷一些 const int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};//四个方向 void print(){ system("cls"); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int ss=2e9; for(int l=0;l<=k;l++) ss=min(ss,dis[i][j][l]); cout<<ss<<" "; } cout<<endl; } }//调试输出函数 void spfa(){//spfa开始 while(!q.empty()){ node u=q.front();q.pop(); int x=u.x,y=u.y,K=u.z;//取出队首元素 if(K==0){//没油了 if(has[x][y]==1){//真棒！这里就有油箱 if(dis[x][y][K]+a<dis[x][y][k]){ dis[x][y][k]=min(dis[x][y][k],dis[x][y][K]+a);//加油花费a q.push(make(x,y,k)); } }else{//这里没有油箱 if(dis[x][y][k]>dis[x][y][K]+c+a){ dis[x][y][k]=min(dis[x][y][k],dis[x][y][K]+c+a);//新建油箱花费c，加油花费a q.push(make(x,y,k)); } } }else{ if(has[x][y]==1){//坑，如果经过油箱必须加油 if(dis[x][y][K]+a<dis[x][y][k]){ dis[x][y][k]=dis[x][y][K]+a;//愉快的花费a q.push(make(x,y,k));continue ;//因为加油，本次状态取消，直接退出 } } for(int i=0;i<4;i++){ int xx=x+dx[i],yy=y+dy[i];//四个方向 if(xx>=1&&xx<=n&&yy>=1&&yy<=n){//判断是否越界 if(dis[xx][yy][K-1]>dis[x][y][K]+((i==1||i==3)?b:0)){//如果往负方向花费b dis[xx][yy][K-1]=dis[x][y][K]+((i==1||i==3)?b:0);//更新 q.push(make(xx,yy,K-1));//保存状态 } } } } // print(); } } int main(){ n=read();k=read();a=read();b=read();c=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ has[i][j]=read(); } }//丑陋无比的读入 memset(dis,63,sizeof(dis));//初始化 dis[1][1][k]=0;//初始化 q.push(make(1,1,k));//塞入队列 spfa();//spfa int ans=2e9;//取最小值前设定最大 for(int i=0;i<=k;i++) ans=min(ans,dis[n][n][i]);//更新，因为终点有很多状态，取最小值 cout<<ans<<endl;//输出 return 0; } |
当然食用spfa啦。
但本蒟蒻不会分层。所以就二维spfa啦。
基本思路就是：一开始先把(1,1)点的状态扔进队列。
然后分类讨论
详细见代码
丑陋无比的代码：
