D - Silver Cow Party J - Invitation Cards 最短路

http://poj.org/problem?id=3268

题目思路：

直接进行暴力，就是先求出举行party的地方到每一个地方的最短路，然后再求以每一个点为源点跑的最短路。

还有一种方法会快很多，就是跑两次最短路，一次正向的，另外一次反向的，因为都是只要求每一个位置到源点的最短距离，

所以这样子写就会快很多。

这个想法看完这个题目在脑袋里一闪而过没有仔细想，后来发现可以直接暴力，就忘记了，结果后面有一个数据大的就不行了。。。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <map>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 2e5 + ;

int d[maxn], dis[maxn], n, m;

struct node

{

    int from, to, dist;

    node(int from=,int to=,int dist=):from(from),to(to),dist(dist){}

};

struct heapnode

{

    int u, d;

    heapnode(int u=,int d=):u(u),d(d){}

    bool operator<(const heapnode&a)const

    {

        return a.d < d;

    }

};

vector<node>vec[maxn];

bool vis[maxn];

void dij(int s)

{

    priority_queue<heapnode>que;

    for (int i = ; i <= n; i++) d[i] = inf;

    d[s] = ;

    memset(vis, , sizeof(vis));

    que.push(heapnode(s, ));

    while(!que.empty())

    {

        heapnode x = que.top(); que.pop();

        int u = x.u;

        if (vis[u]) continue;

        vis[u] = ;

        for(int i=;i<vec[u].size();i++)

        {

            node e = vec[u][i];

            if(d[e.to]>d[u]+e.dist)

            {

                d[e.to] = d[u] + e.dist;

                que.push(heapnode(e.to, d[e.to]));

            }

        }

    }

}

int main()

{

    int k;

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

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

    {

        int x, y, c;

        scanf("%d%d%d", &x, &y, &c);

        vec[x].push_back(node(x, y, c));

    }

    int ans = ;

    dij(k);

    for (int i = ; i <= n; i++) dis[i] = d[i];

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

    {

        if (i == k) continue;

        dij(i);

    //    printf("dis[%d]=%d d[%d]=%d\n", i, dis[i], k, d[k]);

        ans = max(ans, dis[i] + d[k]);

    }

    printf("%d\n", ans);

    return ;

}

http://poj.org/problem?id=1511

这个和上面的题目一个意思

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <map>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e6 + ;

ll d[maxn], dis[maxn];

int n, m;

struct node

{

    int from, to;

    ll dist;

    node(int from = , int to = , ll dist = ) :from(from), to(to), dist(dist) {}

};

struct heapnode

{

    int u;

    ll d;

    heapnode(int u = , ll d = ) :u(u), d(d) {}

    bool operator<(const heapnode&a)const

    {

        return a.d < d;

    }

};

vector<node>vec[maxn];

bool vis[maxn];

void dij(int s)

{

    priority_queue<heapnode>que;

    for (int i = ; i <= n; i++) d[i] = inf;

    d[s] = ;

    memset(vis, , sizeof(vis));

    que.push(heapnode(s, ));

    while (!que.empty())

    {

        heapnode x = que.top(); que.pop();

        int u = x.u;

        if (vis[u]) continue;

        vis[u] = ;

        for (int i = ; i < vec[u].size(); i++)

        {

            node e = vec[u][i];

            if (d[e.to] > d[u] + e.dist)

            {

                d[e.to] = d[u] + e.dist;

                que.push(heapnode(e.to, d[e.to]));

            }

        }

    }

}

int a[maxn], b[maxn];

ll c[maxn];

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

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

        for (int i = ; i <= n; i++) vec[i].clear();

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

        {

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

            vec[a[i]].push_back(node(a[i],b[i],c[i]));

        }

        dij();

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

        {

            dis[i] = d[i];

            vec[i].clear();

        }

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

        {

            vec[b[i]].push_back(node(b[i], a[i], c[i]));

        }

        dij();

        ll ans = ;

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

        {

            ans += d[i] + dis[i];

        }

        printf("%lld\n", ans);

    }

    return ;

}