poj 3463 Sightseeing 将spfa进行到底！！！

谁说这题只能用dijkstra！！！劳资就用spfa + 搜索dp把它秒了！！

不过真tm的难写！！细节之多是难以想象的！！ wa了无数次之后我甚至开始怀疑我的方法的正确性，主要是因为图是多重图啊！！还是有向的啊！！！！dp的时候很恶心，你要考虑自环边！！你要考虑重边！尤其是长度相同的多重边和自环边！！还要考虑长度大1的路径啊。。。考虑各种各样的情况，测试数据不会手下留情！！最恶心的这tm还是搜索dp啊，直接搜索还tle啊！！从昨天搞到现在啊！！睡觉上课走路吃饭都在想啊！！！蓝都用光了啊！！！ac一题真不容易啊...T T

附上一组坑爹数据：

2 17
2 1 1
2 2 1
1 2 2
1 1 1
2 2 2
2 2 2
1 2 2
2 2 2
1 1 1
2 2 1
1 2 1
1 2 1
1 1 2
1 2 1
2 1 1
2 2 2
2 1 2
1 2

answer is 17	

只有2个点，17条边！！多重图相当坑爹！！相当坑爹。。。

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cstdio>
#include<deque>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1111;

struct zz
{
    int from;
    int to;
    int cost;
}zx,tz;
vector<zz>g[maxn];
vector<zz>b[maxn];
deque<int>q;
bool inq[maxn];
int way[maxn];
bool vis[maxn];
bool v2[maxn];
int zh[maxn];
int n,T,m,s,t;
int dp[maxn];
int dp1[maxn];
int num[maxn];

void spfa()
{
    q.clear();
    for(int i=1;i<=n;i++)
    {
        way[i]=inf;
    }
    memset(inq,false,sizeof(inq));
    int now,to,cost;
    q.push_front(s);
    way[s] = 0;
    inq[s] = true;
    while(!q.empty())
    {
        now = q.front();
        q.pop_front();
        for(int i=0;i<g[now].size();i++)
        {
            to =  g[now][i].to;
            cost = g[now][i].cost;
            if(cost + way[now] < way[to])
            {
                way[to] = cost + way[now];
                if(!inq[to])
                {
                    inq[to] = true;
                    if(q.empty())
                    {
                        q.push_front(to);
                    }
                    else if(way[to] < way[q[0]])
                    {
                        q.push_front(to);
                    }
                    else
                    {
                        q.push_back(to);
                    }
                }
            }
        }
        inq[now]=false;
    }
    return ;
}

void init()
{
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            if(g[i][j].to == i && g[i][j].cost == 1)
            {
                num[i]++;
            }
        }
    }
    return ;
}

int dps(int now)
{
    if(vis[now])
    {
        return dp[now];
    }
    int temp,sum=0;
    int from,cost;
    for(int i=0;i<b[now].size();i++)
    {
        from = b[now][i].to;
        if(from==now)
        {
            continue;
        }
        cost = b[now][i].cost;
        if(way[from] + cost == way[now])
        {
            temp = dps(from);
            sum += temp;
        }
    }
    vis[now] = true;
    dp[now] = sum;
    return sum;
}

int df2(int now)
{
    if(v2[now])
    {
        return dp1[now];
    }
    int temp,sum=0;
    int from,cost;
    for(int i=0;i<b[now].size();i++)
    {
        from = b[now][i].to;
        cost = b[now][i].cost;
        if(way[from] + cost == way[now])
        {
            sum += df2(from);
        }
        else if(way[from] + cost == way[now] + 1 )
        {
            if(from != now)
            {
                sum+=dps(from);
            }
        }
    }
    sum += num[now]*dps(now);
    dp1[now] = sum;
    v2[now] = true;
    return sum;
}



int dpstart()
{
    spfa();
    init();
    memset(dp,0,sizeof(dp));
    memset(dp1,0,sizeof(dp1));
    memset(vis,false,sizeof(vis));
    memset(v2,false,sizeof(v2));
    vis[s]=true;
    dp[s]=1;
    int ans=0;
    ans += dps(t);
    v2[s] = true;
    dp1[s] = num[s];
    ans += df2(t);
    return ans;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<maxn;i++)
        {
            g[i].clear();
            b[i].clear();
        }
        for(int i=1;i<=m;i++)
        {
            cin>>zx.from>>zx.to>>zx.cost;
            g[zx.from].push_back(zx);
            swap(zx.from,zx.to);
            b[zx.from].push_back(zx);
        }
        cin>>s>>t;
        cout<<dpstart()<<endl;
    }
    return 0;
}