lightoj 1074

这题怎么说呢，负环上的点都不行

网上也有很多解法

我用dfs的spfa解的

我发现网上别人的代码都是用bfs的spfa写的，我就用的dfs的，快了好多

代码还看的别人的，只有中间的spfa是自己写的

我自己原来写的不知道为什么就过不了

把别人的spfa换成自己的就过了

这个是ac的：

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<stack>

#include<queue>

using namespace std;

const int N = ;

const int MAX = 0x3f3f3f3f;

int dis[N];

int p[N];

int h[N];

int cnt[N];

bool vis[N];

bool r[N];

int c[N];

struct Node

{

    int u, v, w, next;

}e[N*N];

void dfs(int x)

{

    r[x] = ;

    for(int i=h[x]; i!=-; i=e[i].next)

        if(!r[e[i].v])

            dfs(e[i].v);

}

void spfa(int u)

{

    if(r[u])

        return ;

    vis[u] = true;

    for(int i = h[u]; i != -; i = e[i].next)

    {

        int v,w;

        v = e[i].v;

        w = e[i].w;

        if(dis[v] > dis[u] + w)

        {

            dis[v] = dis[u]+w;

            if(vis[v])

            {

                dfs(v);

                return ;

            }

            else

            {

                spfa(v);

            }

        }

    }

    vis[u] = false;

}

int main()

{

    int T;

    scanf("%d", &T);

    for(int tt=; tt<=T; tt++)

    {

        int n, m;

        scanf("%d", &n);

        memset(cnt, , sizeof(cnt));

        memset(vis, , sizeof(vis));

        memset(r, , sizeof(r));

        memset(dis, 0x3f3f3f3f, sizeof(dis));

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

            scanf("%d", &p[i]);

        scanf("%d", &m);

        memset(h, -, sizeof(h));

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

        {

            int a, b;

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

            e[i].u = a;

            e[i].v = b;

            e[i].w = (p[b]-p[a])*(p[b]-p[a])*(p[b]-p[a]);

            e[i].next = h[a];

            h[a] = i;

        }

        int Q;

        scanf("%d", &Q);

        for(int i=; i<Q; i++)

            scanf("%d", &c[i]);

        printf("Case %d:\n", tt);

        dis[] = ;

        spfa();

        for(int i=; i<Q; i++)

        {

            int to = c[i];

            if(dis[to]==MAX || r[to] || dis[to] < )

                printf("?\n");

            else

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

        }

    }

    return ;

}

这个是wa的，那位dalao帮我抓抓虫啊，真的苦，我看了半天楞是没看出来

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = ;

const int INF = 0x3f3f3f3f;

int n,m;

int cnt;

struct node

{

    int v,w;

};

bool vis[maxn];

int head[maxn];

int nex[maxn];

node e[maxn*maxn];

int dis[maxn];

int busy[maxn];

bool vis2[maxn];

int c[maxn];

void adde(int u,int v,int w)

{

    node t;

    t.v = v;

    t.w = w;

    e[cnt] = t;

    nex[cnt] = head[u];

    head[u] = cnt ++;

}

void spfa(int u);

void dfs(int u);

int main()

{

    int t;

    scanf("%d",&t);

    for(int k = ; k <= t; ++k)

    {

        memset(vis2,,sizeof(vis2));

        memset(dis,0x3f,sizeof(dis));

        memset(vis,,sizeof(vis));

        memset(head,-,sizeof(head));

        //memset(cn,0,sizeof(cn));

        memset(nex,-,sizeof(nex));

        memset(e,,sizeof(e));

        cnt = ;

        scanf("%d",&n);

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

            scanf("%d",busy+i);

        scanf("%d",&m);

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

        {

            int a,b;

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

            int c = (busy[b] - busy[a])*(busy[b] - busy[a])*(busy[b] - busy[a]);

            adde(a,b,c);

        }

        int Q;

        scanf("%d",&Q);

        for(int i = ; i < Q; ++i)

            scanf("%d",c+i);

        printf("Case %d:\n", k);

        dis[] = ;

        spfa();

        for(int i = ; i < Q; ++i)

        {

            if(dis[c[i]] == INF || vis2[c[i]] || dis[c[i]] < )

                printf("?\n");

            else

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

        }

    }

    return ;

}

void spfa(int u)

{

    if(vis2[u])

        return ;

    vis[u] = true;

    for(int i = head[u]; i != -; i = nex[i])

    {

        int v,w;

        v = e[i].v;

        w = e[i].w;

        if(dis[v] > dis[u] + w)

        {

            dis[v] = dis[u]+w;

            if(vis[v])

            {

                dfs(v);

                return ;

            }

            else

            {

                spfa(v);

            }

        }

    }

    vis[u] = false;

}

void dfs(int u)

{

    vis2[u] = true;

    for(int i = head[u]; i != -; i = nex[i])

    {

        int v = e[i].v;

        if(vis2[v] == false)

            dfs(v);

    }

}