学步园

点击打开链接

两次求最短路（第二次把边反向求）

1、spfa

//poj 3268 Silver Cow Party
//SPFA

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int M = 100000 + 100;
const int N = 1000 + 100;
const int inf = 1<<25;



struct Graph {
    int head[N], next[M], to[M], val[M], cnt, n;

    void init(int num)
    {
        memset(head, -1, sizeof head );
        for(int i=1; i<=n; ++i) d[i] = inf;
        cnt = 0;
        n = num;
        while(!q.empty()) q.pop();
    }

    void addedge(int u, int v, int c)
    {
        next[cnt] = head[u];
        to[cnt] = v;
        val[cnt] = c;
        head[u ] = cnt++;
    }

    int d[N], vis[M];
    queue<int> q;

    void spfa(int s)
    {
        memset(vis, 0, sizeof vis );
        d[s] = 0;
        vis[s] = 1;
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i=head[u]; ~i; i = next[i]) {
                int v = to[i];
                if(d[v] > d[u] + val[i]) {
                    d[v] = d[u] + val[i];
                    if(!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
            vis[u] = 0;
        }
    }
} g1, g2;

int n, m, x;

int main()
{
    while(~scanf("%d%d%d", &n, &m, &x)) {
        g1.init(n);
        g2.init(n);
        int u, v, c;
        for(int i=1; i<=m; ++i){
           scanf("%d%d%d", &u, &v, &c);
           g1.addedge(u, v, c);
           g2.addedge(v, u, c);
        }

        g1.spfa(x); g2.spfa(x);

        int ans = 0;
        for(int i=1; i<=n; ++i)
        {
            if(i != x)
            {
                if(g1.d[i] != inf && g2.d[i] != inf)
                {
                    if(ans < g1.d[i] + g2.d[i])
                        ans = g1.d[i] + g2.d[i];
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

2、dijkstra

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int M = 100000 + 100;
const int N = 1000 + 100;
const int inf = 1<<25;
typedef pair<int, int> P;
int n, m, x;


struct node {
    int v;
    int c;
    node(int vv=0, int cc=0): v(vv), c(cc) {}
    /*
    bool operator < (const node& r) const
    {
        return c > r.c;
    }
    */
};


struct Graph
{
    int head[N], next[M], to[M], val[M], cnt, n;


    void init(int nv)
    {
        memset(head, -1, sizeof head );
        n = nv;
        for(int i=1; i<=n; ++i) d[i] = inf;
        cnt = 0;
        while(!q.empty()) q.pop();
    }


    void addedge(int u, int v, int c)
    {
        next[cnt] = head[u];
        to[cnt] = v;
        val[cnt] = c;
        head[u] = cnt++;
    }


    int d[N];
    priority_queue<P, vector<P>, greater<P> > q;


    void dijkstra(int s)
    {
        d[s] = 0;
        q.push(P(0,s));
        while(!q.empty()){
            P p = q.top();
            q.pop();
            int v = p.second;
            if(d[v]<p.first) continue;
            for(int i=head[v]; ~i; i =next[i])
            {
                int k = to[i];
                if(d[k] > d[v] + val[i])
                {
                    d[k] = d[v] + val[i];
                    q.push(P(d[k], k));
                }
            }
        }
    }


}s1, s2;


int main()
{
    int u, v, c;
    scanf("%d%d%d", &n, &m, &x);
    s1.init(n); s2.init(n);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d%d", &u, &v, &c);
        s1.addedge(u, v, c);
        s2.addedge(v, u, c);
    }
    s1.dijkstra(x);
    s2.dijkstra(x);
    int ans = 0;
    for(int i=1; i<=n; ++i)
    {
        if(i==x) continue;
        if(s1.d[i] + s2.d[i] > ans)
            ans = s1.d[i] + s2.d[i];
    }
    printf("%d\n", ans);
    return 0;
}