首页 > 代码库 > boj 454 帮帮小叮当【SPFA】
boj 454 帮帮小叮当【SPFA】
题目链接：http://code.bupt.edu.cn/problem/p/454/
454. 帮帮小叮当
时间限制5000 ms内存限制 65536 KB
题目描述
小叮当刚刚学会了传送门的使用方法，可是它不小心跌落到二维空间一个 n * m 的矩阵格子世界的入口（1,1）处，
他得知出口在（n,m）处，每穿越一个格子门，它的体力值会下降。
又饿又累的他 IQ 已经降为负数了，聪明的你，能帮他规划一下路线，使得它体力值下降的最少吗？
每一行有且仅有一个传送门，但是小叮当上课睡着了，只学会了用传送门瞬移到相邻行的另一个传送门且耗 1 滴体力。
此外，他就只能通过格子门走到相邻四个格子中的一个，也耗 1 滴体力。
ps,由于符合的路径太多了，你只需要告诉我们体力值消耗最小值。
输入格式
每组数据，第一行给 n,m 两个整数（2 <= n,m <= 10000），接下来一行，有 n 个数字，代表该行传送门的位置 x( 1 <= x <= m )。以 n,m 都为0结束。Mays温馨提醒：数据组数略大于100。
输出格式
对每组输入，输出一行，体力消耗最小值。
输入样例
5 5
5 4 3 2 1
0 0输出样例
8五角星代表传送阵，圆圈代表起点和终点。由于要求最小的距离，那么，除了样例给出的极端情况以外，走传送门一定是可以节省体力的，那么，以起点到各传送门，传送门到传送门，传送门到终点建边，而边的权值为两点间的曼哈顿距离，传送门之间的边的权值都为1,。之后求出最短路径即可。
之前图论基础几乎为0....这次第一次用SPFA，解出来还是挺开心的^_^
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#define N 400100
using namespace std;
struct edge
{
int from,to,c,nxt;
}e[N];
int head[N];
int d[N];
int s;
bool vis[N];
int n,m;
int dist(int x,int y,bool S)
{
if(S)
return abs(x-1)+abs(y-1);
else
return abs(x-n)+abs(y-m);
}
void spfa(int s)
{
queue<int> q;
memset(d,0x3f,sizeof(d));
d[s]=0;
memset(vis,0,sizeof(vis));
q.push(s);
vis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for(int k=head[x];k!=-1;k=e[k].nxt)
{
if(d[e[k].to]>d[e[k].from]+e[k].c)
{
d[e[k].to]=d[e[k].from]+e[k].c;
if(!vis[e[k].to])
{
vis[e[k].to]=1;
q.push(e[k].to);
}
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m))
{
memset(head,-1,sizeof(head));
int t=1,last;
for(int i=0;i<4*n-2;)
{
int temp;
scanf("%d",&temp);
e[i].from=0;
e[i].to=t;
e[i].c=dist(t,temp,1);
e[i].nxt=head[0];
head[0]=i++;
e[i].from=t;
e[i].to=n+1;
e[i].c=dist(t,temp,0);
e[i].nxt=head[t];
head[t]=i++;
if(i!=2)
{
e[i].from=t;
e[i].to=t-1;
e[i].c=1;
e[i].nxt=head[t];
head[t]=i++;
e[i].from=t-1;
e[i].to=t;
e[i].c=1;
e[i].nxt=head[t-1];
head[t-1]=i++;
}
t++;
}
spfa(0);
printf("%d\n",d[n+1]);
}
return 0;
}
下面是dijkstra的代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#define N 400100
using namespace std;
struct dij
{
int id,dist;
bool operator < (const dij s1) const
{
return dist>s1.dist;
}
};
struct edge
{
int from,to,c,nxt;
}e[N];
priority_queue<dij> q;
int head[N];
int d[N];
int s;
bool vis[N];
int n,m;
void dijkstra()
{
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
for(int i=0;i<n+2;i++) d[i]=99999999;
d[0]=0;
dij ss,tt;
ss.id=0;
ss.dist=0;
vis[ss.id]=true;
q.push(ss);
while(!q.empty())
{
tt=q.top();
q.pop();
int id=tt.id,dist=tt.dist;
vis[id]=true;
for(int k=head[id];k!=-1;k=e[k].nxt)
{
if(!vis[e[k].to] && d[e[k].to]>d[id]+e[k].c)
{
d[e[k].to]=d[id]+e[k].c;
ss.id=e[k].to;
ss.dist=d[e[k].to];
q.push(ss);
}
}
}
}
int dist(int x,int y,bool S)
{
if(S)
return abs(x-1)+abs(y-1);
else
return abs(x-n)+abs(y-m);
}
//void spfa(int s)
//{
// queue<int> q;
// memset(d,0x3f,sizeof(d));
// d[s]=0;
// memset(vis,0,sizeof(vis));
//
// q.push(s);
// vis[s]=1;
// while(!q.empty())
// {
// int x=q.front();
// q.pop();
// vis[x]=0;
// for(int k=head[x];k!=-1;k=e[k].nxt)
// {
// if(d[e[k].to]>d[e[k].from]+e[k].c)
// {
// d[e[k].to]=d[e[k].from]+e[k].c;
// if(!vis[e[k].to])
// {
// vis[e[k].to]=1;
// q.push(e[k].to);
// }
// }
// }
// }
//
//}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m))
{
memset(head,-1,sizeof(head));
int t=1,last;
for(int i=0;i<4*n-2;)
{
int temp;
scanf("%d",&temp);
e[i].from=0;
e[i].to=t;
e[i].c=dist(t,temp,1);
e[i].nxt=head[0];
head[0]=i++;
e[i].from=t;
e[i].to=n+1;
e[i].c=dist(t,temp,0);
e[i].nxt=head[t];
head[t]=i++;
if(i!=2)
{
e[i].from=t;
e[i].to=t-1;
e[i].c=1;
e[i].nxt=head[t];
head[t]=i++;
e[i].from=t-1;
e[i].to=t;
e[i].c=1;
e[i].nxt=head[t-1];
head[t-1]=i++;
}
t++;
}
dijkstra();
printf("%d\n",d[n+1]);
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。