spfa毒瘤算法

终于知道怎么卡spfa(不优化)这一毒瘤算法了

下面就是造数据代码,点数才1e5,边数379980

随便测了一组数据:

count: 831841219(入队次数)

68917.096 ms(足够t到死了)

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define fio ios::sync_with_stdio(false);cin.tie(0)

template<typename T>

inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>

inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=100000+10,maxn=400000+10,inf=0x3f3f3f3f;

struct edge{int a,b,c;};

vector<edge>v;

int main()

{

    srand(time(0));

    freopen("a.txt","w",stdout);

    int n=10,m=10000;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            if(j!=m)

            {

                v.pb({(i-1)*m+j,(i-1)*m+j+1,rand()%100000+1});

                v.pb({(i-1)*m+j+1,(i-1)*m+j,rand()%100000+1});

            }

            if(i!=n)

            {

                v.pb({(i-1)*m+j,i*m+j,1});

                v.pb({i*m+j,(i-1)*m+j,1});

            }

        }

    }

    printf("%d %d\n",n*m,v.size());

    random_shuffle(v.begin(),v.end());

    for(int i=0;i<v.size();i++)

        printf("%d %d %d\n",v[i].a,v[i].b,v[i].c);

    return 0;

}

/********************

********************/

spfa代码

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define fio ios::sync_with_stdio(false);cin.tie(0)

template<typename T>

inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>

inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=1000000+10,maxn=4000000+10,inf=0x3f3f3f3f;

struct edge{

    int to,Next,c;

}e[maxn];

int cnt,head[N];

void init()

{

    cnt=0;

    memset(head,-1,sizeof head);

}

void add(int u,int v,int c)

{

    e[cnt].to=v;

    e[cnt].c=c;

    e[cnt].Next=head[u];

    head[u]=cnt++;

}

bool vis[N];

ll dis[N];

void spfa()

{

    memset(vis,0,sizeof vis);

    memset(dis,INF,sizeof dis);

    vis[1]=1;dis[1]=0;

    queue<int>q;

    q.push(1);

    int co=0;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        vis[u]=0;

        for(int i=head[u];~i;i=e[i].Next)

        {

            int x=e[i].to;

            if(dis[x]>dis[u]+e[i].c)

            {

                dis[x]=dis[u]+e[i].c;

                if(!vis[x])

                {

                    vis[x]=1;

                    q.push(x);

                    co++;

                }

            }

        }

    }

    printf("count: %d\n",co);

}

int main()

{

    int a=clock();

    freopen("a.txt","r",stdin);

    init();

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

    }

    spfa();

    printf("%d\n",dis[n]);

    int b=clock();

    printf("%.3f ms\n",1.0*(b-a)/1000);

    return 0;

}

/********************

********************/