Spfa&bellman-ford


最短路Spfa

Spfa的写法

bfs正规spfa

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string.h>
#define N 16000
using namespace std;
int n,m,s,dim[N],vis[N];
struct node
{
    int to,w;
    struct node *next;
}e[N];
queue<int>q;
/*bool operator<(node a,node b)
{
    if(a.w==b.w)return a.to>b.to;
    return a.w>b.w;
}*/
void add(int x,int y,int w)
{
    node *p=(node *)malloc(sizeof(node));
    *p=e[x],e[x].to=y,e[x].w=w,e[x].next=p;
}
void spfa()
{
    q.push(s);
    while(!q.empty())
    {
        int top=q.front();q.pop();vis[top]=false;
        node *p=&e[top];
        while(p!=NULL)
        {
            if(p->w+dim[top]<dim[p->to])
            {
                if(!vis[p->to])
                    q.push(p->to),vis[p->to]=true;
                dim[p->to]=p->w+dim[top];
            }
            p=p->next;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int fi,gi,wi;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&fi,&gi,&wi);
        add(fi,gi,wi);
    }
    for(int i=1;i<=n;i++)dim[i]=2147483647;
    dim[s]=0;
    spfa();
    for(int i=1;i<=n;i++)
        printf("%d ",dim[i]);
    return 0;
}

对比一下dfs(负环过了,单源最短路TLE6个点)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string.h>
#define N 220000
using namespace std;
int n,m,s,dim[N],vis[N],thistime[N],check,t;
struct node
{
    int to,w;
    struct node *next;
}e[N];
//priority_queue<node>q;
/*bool operator<(node a,node b)
{
    if(a.w==b.w)return a.to>b.to;
    return a.w>b.w;
}*/
void add(int x,int y,int w)
{
    node *p=(node *)malloc(sizeof(node));
    *p=e[x],e[x].to=y,e[x].w=w,e[x].next=p;
}
void spfa(int src)
{
    t++;
    //if(thistime[src]){check=true;return;}
    //thistime[src]=true;
    //vis[src]=1;
    node *p;
    p=(node *)malloc(sizeof(node));
    *p=e[src];
    //vis[p->to]=1;
    while(p->next!=NULL)
    {
        //p->w+=dim[src];
        //if(!vis[p->to])q.push(*p);
        node minium=*p;
        minium.w+=dim[src];
        p=p->next;
        if(dim[minium.to]<=minium.w)continue;
        else dim[minium.to]=minium.w;
        //vis[minium.to]=1;
        //q.pop();
        spfa(minium.to);
    }
    //thistime[src]=false;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int fi,gi,wi;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&fi,&gi,&wi);
        add(fi,gi,wi);
    }
    for(int i=1;i<=n;i++)dim[i]=2147483647;
        spfa(s);
    for(int i=1;i<=n;i++)printf("%d ",dim[i]);
    return 0;
}

区别

- bfs是将目前搜到的点所连的边加入搜索队列,堆优化后每次取最短的边进行松弛,dfs需要一回走到底,每条分支都进行更新,相当于剪枝搜索。因此dfs对于每个点需要多次更新,时间复杂度远大于bfs。

相关题目

1. USACO题目热浪Heat Wave

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string.h>
#define N 16000
using namespace std;
int n,m,s,t,dim[N],vis[N];
struct node
{
    int to,w;
    struct node *next;
}e[N];
priority_queue<node>q;
bool operator<(node a,node b)
{
    if(a.w==b.w)return a.to>b.to;
    return a.w>b.w;
}
void add(int x,int y,int w)
{
    node *p=(node *)malloc(sizeof(node));
    *p=e[x],e[x].to=y,e[x].w=w,e[x].next=p;
}
void spfa(int src)
{
    if(vis[src])return;
    vis[src]=1;
    node *p;
    p=(node *)malloc(sizeof(node));
    *p=e[src];
    //vis[p->to]=1;
    while(p->next!=NULL)
    {
        p->w+=dim[src];
        if(!vis[p->to])q.push(*p);
        p=p->next;
    }
    while(!q.empty())
    {
    node minium=q.top();
    //vis[minium.to]=1;
    dim[minium.to]=min(dim[minium.to],minium.w);
    q.pop();
    spfa(minium.to);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int fi,gi,wi;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&fi,&gi,&wi);
        add(fi,gi,wi);
        add(gi,fi,wi);
    }
    for(int i=1;i<=n;i++)dim[i]=2147483647;
    dim[s]=0;//vis[s]=1;
    spfa(s);
    printf("%d",dim[t]);
    return 0;
}

这是D(B)FS(逃。

我的写法太不标准。。。

2. USACO题目回家Bessie Come Home

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string.h>
#define N 16000
using namespace std;
int n,m,s,dim[N],vis[N],ans=2147483647,wi;
char fi,gi,farm;
struct node
{
    int to,w;
    struct node *next;
}e[N];
priority_queue<node>q;
bool operator<(node a,node b)
{
    if(a.w==b.w)return a.to>b.to;
    return a.w>b.w;
}
void add(int x,int y,int w)
{
    node *p=(node *)malloc(sizeof(node));
    *p=e[x],e[x].to=y,e[x].w=w,e[x].next=p;
}
void spfa(int src)
{
    if(vis[src])return;
    vis[src]=1;
    node *p;
    p=(node *)malloc(sizeof(node));
    *p=e[src];
    while(p->next!=NULL)
    {
        p->w+=dim[src];
        if(!vis[p->to])q.push(*p);
        p=p->next;
    }
    while(!q.empty())
    {
    node minium=q.top();
    dim[minium.to]=min(dim[minium.to],minium.w);
    q.pop();
    spfa(minium.to);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>fi>>gi>>wi;
        //字符、空格、数字输入,反正数据不多,就用cin了。
        add((int)fi,(int)gi,wi);
        add((int)gi,(int)fi,wi);
    }
    for(int i=65;i<=127;i++)dim[i]=21474836;
    dim[90]=0;//'Z'为源点。
    spfa(90);
    dim[90]=2147483647;//排除'Z'谷仓。
    for(int i=65;i<=90;i++)//不用考虑a-z。
    if(dim[i]<ans){ans=dim[i];farm=i;}
    cout<<farm<<' '<<ans;
    return 0;
}

比较水的题,我在数据读入卡半天,最后一想,直接cin就好了

就是把a-z和A-Z对应到点,然后就是[模板]了。