P4554 小明的游戏,P1744 采购特价商品(spfa)

https://www.luogu.com.cn/problem/P4554
P4554 小明的游戏
spfa
从二维表中建图，本题根据题意若相邻的符号相同则赋值为0，不同则赋值为1，利用spfa求最短路

#include <bits/stdc  .h>
#define y1 y11
using namespace std;
const int maxn=6e6 5;
const int inf=0x3f3f3f3f;
char mp[505][505];
int n,m,head[maxn],cnt,x1,y1,x2,y2,dist[maxn];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool vis[maxn];
struct node
{
    int  to,nxt,dis;
}e[maxn];

void add(int from,int to,int dis)
{
    e[  cnt].to=to;
    e[cnt].dis=dis;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
queue<int>q;
void spfa(int u)
{
    memset(dist,inf,sizeof(dist));
    dist[u]=0;
    q.push(u);
    vis[u]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];~i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dist[y]>dist[x] e[i].dis)
            {
                dist[y]=dist[x] e[i].dis;
                if(!vis[y])
                {
                    vis[y]=1;q.push(y);
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i  )
            for(int j=1;j<=m;j  )
            cin>>mp[i][j];
        for(int i=1;i<=n;i  )
        {
            for(int j=1;j<=m;j  )
            {
                for(int k=0;k<4;k  )
                {
                    int nx=i dx[k],ny=j dy[k];
                    if(nx<=0||nx>n||ny<=0||ny>m)
                        continue;
                    if(mp[nx][ny]==mp[i][j])
                    {
                        add(i*m j,nx*m ny,0);
                    }
                    else
                        add(i*m j,nx*m ny,1);
                }
            }
        }
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1 =1;y1 =1;x2 =1;y2 =1;
        spfa(x1*m y1);
        cout<<dist[x2*m y2]<<endl;
    }
    return 0;
}

P1744 采购特价商品
spfa的模板题，距离稍微变形了一下
https://www.luogu.com.cn/problem/P1744

#include <bits/stdc  .h>
using namespace std;
const int maxn=1e5 5;
int n,m,s,t,a[maxn],b[maxn],head[maxn],cnt;
bool vis[maxn];
double dist[maxn];
struct node
{
    int  to,nxt;
    double dis;
}e[maxn];
double dd(int x1,int y1,int x2,int y2)
{
    double tmp=sqrt((x1-x2)*(x1-x2)*1.0 (y1-y2)*(y1-y2)*1.0);
    //cout<<tmp<<endl;
    return tmp;
}
void add(int from,int to,double dis)
{
    e[  cnt].to=to;
    e[cnt].dis=dis;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
queue<int>q;
void spfa(int u)
{
    for(int i=1;i<=n;i  )
        dist[i]=1000000.00;
    dist[u]=0;
    q.push(u);vis[u]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dist[y]>dist[x] e[i].dis)
            {
                dist[y]=dist[x] e[i].dis;
                if(!vis[y])
                {
                    vis[y]=1;q.push(y);
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i  )
        scanf("%d%d",&a[i],&b[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i  )
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v,dd(a[u],b[u],a[v],b[v]));
        add(v,u,dd(a[u],b[u],a[v],b[v]));
    }
    scanf("%d%d",&s,&t);
    spfa(s);
    printf("%.2lf\n",dist[t]);
    return 0;
}

这篇好文章是转载于：学新通技术网