[POJ 3463] Sightseeing

[题目链接]

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

[算法]

        最短路

#include <algorithm>  
#include <bitset>  
#include <cctype>  
#include <cerrno>  
#include <clocale>  
#include <cmath>  
#include <complex>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <ctime>  
#include <deque>  
#include <exception>  
#include <fstream>  
#include <functional>  
#include <limits>  
#include <list>  
#include <map>  
#include <iomanip>  
#include <ios>  
#include <iosfwd>  
#include <iostream>  
#include <istream>  
#include <ostream>  
#include <queue>  
#include <set>  
#include <sstream>  
#include <stdexcept>  
#include <streambuf>  
#include <string>  
#include <utility>  
#include <vector>  
#include <cwchar>  
#include <cwctype>  
#include <stack>  
#include <limits.h>
using namespace std;
#define MAXN 2010
#define MAXM 20010
const int INF = 2e9;

struct edge
{
        int to,w,nxt;
} e[MAXM << 1];

int i,n,m,ans,tot,tmp,val,shortest,S,T,TC;
int head[MAXN],rhead[MAXN],u[MAXM],v[MAXM],w[MAXM],
        dista[MAXN],distb[MAXN],cnta[MAXN],cntb[MAXN];

inline void addedge(int u,int v,int w)
{
        tot++;
        e[tot] = (edge){v,w,head[u]};
        head[u] = tot;
}
inline void addredge(int u,int v,int w)
{
        tot++;
        e[tot] = (edge){v,w,rhead[u]};
        rhead[u] = tot;
}
inline void spfa1(int s)
{
        int i,l,r,u,v,w;
        static int q[MAXN];
        static bool inq[MAXN];
        for (i = 1; i <= n; i++) 
        {
                dista[i] = INF;
                inq[i] = false;
        }
        q[l = r = 1] = s;
        inq[s] = true;
        dista[s] = 0; 
        while (l <= r)
        {
                u = q[l];
                l++;
                inq[u] = false;
                for (i = head[u]; i; i = e[i].nxt)
                {
                        v = e[i].to;
                        w = e[i].w;
                        if (dista[u] + w < dista[v])
                        {
                                dista[v] = dista[u] + w;
                                if (!inq[v])
                                {
                                        inq[v] = true;
                                        q[++r] = v;
                                }
                        } 
                }
        }
}
inline void spfa2(int s)
{
        int i,l,r,u,v,w;
        static int q[MAXN];
        static bool inq[MAXN];
        for (i = 1; i <= n; i++)
        {
                distb[i] = INF;
                inq[i] = false;
        }
        q[l = r = 1] = s;
        distb[s] = 0; 
        inq[s] = true;
        while (l <= r)
        {
                u = q[l];
                l++;
                inq[u] = false;
                for (i = rhead[u]; i; i = e[i].nxt)
                {
                        v = e[i].to;
                        w = e[i].w;
                        if (distb[u] + w < distb[v])
                        {
                                distb[v] = distb[u] + w;
                                if (!inq[v])
                                {
                                        inq[v] = true;
                                        q[++r] = v;
                                }
                        } 
                }
        }
}
inline int dp1(int u)
{
        int i,v,w;
        if (cnta[u] != -1) return cnta[u];
        if (u == S) return cnta[u] = 1;
        cnta[u] = 0;
        for (i = rhead[u]; i; i = e[i].nxt)
        {
                v = e[i].to;
                w = e[i].w;
                if (dista[v] + w == dista[u]) cnta[u] += dp1(v);
        }
        return cnta[u];
}
inline int dp2(int u)
{
        int i,v,w;
        if (cntb[u] != -1) return cntb[u];
        if (u == T) return cntb[u] = 1;
        cntb[u] = 0;
        for (i = head[u]; i; i = e[i].nxt)
        {
                v = e[i].to;
                w = e[i].w;
                if (dista[u] + w == dista[v]) cntb[u] += dp2(v);
        }
        return cntb[u];
}
int main() 
{
        
        scanf("%d",&TC);
        while (TC--)
        {
                scanf("%d%d",&n,&m);
                tot = 0;
                for (i = 1; i <= n; i++) 
                {
                        head[i] = rhead[i] = 0;
                        cnta[i] = cntb[i] = -1;
                }
                for (i = 1; i <= m; i++)
                {
                        scanf("%d%d%d",&u[i],&v[i],&w[i]);
                        addedge(u[i],v[i],w[i]);
                        addredge(v[i],u[i],w[i]);
                }        
                scanf("%d%d",&S,&T);
                spfa1(S);
                spfa2(T);
                for (i = 1; i <= n; i++) dp1(i);
                for (i = 1; i <= n; i++) dp2(i);
                shortest = dista[T];
                ans = cnta[T];
                for (i = 1; i <= m; i++)
                {
                        tmp = dista[u[i]] + w[i] + distb[v[i]];
                        if (dista[u[i]] + w[i] == dista[v[i]] + 1 && tmp == shortest + 1) ans += cnta[u[i]] * cntb[v[i]];
                }
                printf("%d\n",ans);
        }
        
        return 0;
    
}